Hai bisogno di chiarimenti riguardo ai certificati dei problemi coNP

Question

NOTA:questo è non un tentativo di dimostrare $NP eq coNP$

C'è una cosa che non sono mai riuscito a digerire completamente riguardo ai certificati di problemi $coNP$ e apprezzerei molto un chiarimento definitivo da parte di questa comunità.

Concentriamoci sul problema della somma dei sottoinsiemi ($SOMMA$), ora sappiamo tutti che esiste questo problema $NP$ Dal momento che, per accettare l'appartenenza alla lingua, un Prover $P_v$ può emettere un certificato che funge da verificatore $V_r$ può controllare in tempo polinomiale.Fino a qui nessun problema.Il complemento di questo problema ($\overline{SUBSUM}$) è dentro $coNP$ il che significa che non sappiamo se esiste un conciso (cioè polinomiale) certificato per decidere la lingua.Se tale certificato non esiste, allora $NP eq coNP$ e quindi $P eq NP$.Quello che non capisco è questo:

Se ho (ad esempio) un set $S$ di numeri interi e il numero $0$ come input e chiedo:Dimostramelo $\forall s \in S \space\space\lnot SUBSUM$, cioè $ eesiste$ un sottoinsieme di $S$ tale che la somma dei suoi elementi dia $0$ di conseguenza (questo è $\overline{SUBSUM}$, il complemento del problema del sottoinsieme).Come può esistere un certificato per questo problema di cui è presente la verifica $P$?Voglio dire, devo dimostrarlo per tutto il sottoinsieme, quindi lo spazio di ricerca deve essere il powerset di $S$.Se $|S|=n$ Poi $\mathcal{|P(S)|}=2^n$.Quindi se il prover, ad esempio, produce a $2^{n/3}$ certificato, questo significa che tralascio sistematicamente $2^{ \frac{2}{3}n}$ sottoinsiemi.Ciò che non capisco del tutto e per il quale ho bisogno di chiarimenti è il motivo per cui questo argomento non viene accettato come prova di ciò $NP$ non è chiuso rispetto al complemento.

Answer 1

La prova è che il bot deve essere un sottoinsieme.Potrebbe essere un altro indicatore del fatto che l'insieme dato presenta alcune restrizioni che gli impediscono di essere un esempio positivo del problema dei sottoinsiemi.Un buon esempio con un certificato non banale è la programmazione lineare.I programmi lineari ammettono sia un certificato positivo che uno negativo (per la domanda se l'ottimale può essere minore/maggiore di un valore k).L'istanza positiva è ovviamente un'assegnazione della variabile.Il negativo però è dato dal lemma di Faraks e dalla dualità debole.

Un buon esercizio per te è cercare i programmi lineari, la dualità debole e il lemma di Farkas :)