Necessita de esclarecimentos sobre certificados de problemas de coNP

Question

OBSERVAÇÃO:isso é não uma tentativa de provar $NP eq coNP$

Há uma coisa que nunca consegui digerir completamente sobre os certificados de problemas em $coNP$ e eu apreciaria muito um esclarecimento definitivo desta comunidade.

Vamos nos concentrar no problema da soma do subconjunto ($SUBSUM$), agora todos sabemos que este problema está em $NP$ Desde que, para aceitar a associação ao idioma, um provador $P_v$ pode emitir um certificado que um verificador $V_r$ pode verificar em tempo polinomial.Até aqui não há problema.O complemento deste problema ($\overline{SUBSUM}$) é em $coNP$ o que significa que não sabemos se há um sucinto (ou seja, polinomial) certificado para decidir o idioma.Se tal certificado não existir, então $NP eq coNP$ e portanto $P eq NP$.O que não entendo é o seguinte:

Se eu tiver (por exemplo) um conjunto $S$ de inteiros e o número $0$ como entrada e pergunto:Prove-me isso $\forall s \in S \space\space\lnot SUBSUM$, ou seja $\existe$ um subconjunto de $S$ tal que a soma do seu elemento dá $0$ como resultado (isso é $\overline{SUBSUM}$, o complemento do problema do subconjunto).Como pode existir um certificado para este problema cuja verificação está em $P$?Quero dizer, preciso provar isso para todo o subconjunto, então o espaço de busca deve ser o conjunto de potências de $S$.Se $|S|=n$ então $\mathcal{|P(S)|}=2^n$.Então, se o provador, por exemplo, produzir um $2^{n/3}$ certificado, isso significa que eu sistematicamente deixo de fora $2^{\frac{2}{3}n}$ subconjuntos.O que não entendo completamente e para o qual preciso de esclarecimento é por que este argumento não é aceito como prova de que $NP$ não está fechado no complemento.

Answer 1

A prova de que o bot precisa ser um subconjunto.Pode ser outro indicador de que um determinado conjunto possui alguma restrição que o impede de ser uma instância positiva do problema dos subconjuntos.Um bom exemplo de certificado não trivial é a programação linear.Os programas lineares admitem um certificado positivo e um negativo (para a questão se o ótimo pode ser menor/maior que um valor k).A instância positiva é obviamente uma atribuição da variável.O negativo, entretanto, é dado pelo lema de Faraks e pela dualidade fraca.

Um bom exercício para você é procurar programas lineares, dualidade fraca e lema de Farkas :)