Besoin de clarification concernant les certificats de problèmes de CONP

Question

note : ceci est pas une tentative de prouver $ n \ neq conique $

Il y a une chose que je n'ai jamais réussi à digérer complètement sur les certificats de problèmes dans $ ConP $ et j'apprécierais beaucoup une clarification définitive de cette communauté .

Concentrons sur le problème du sous-ensemble Problème ( $ SUBSTUM $ ), nous savons maintenant que ce problème est dans $ Np $ depuis, Pour accepter l'adhésion à la langue, un prouveur $ p_v $ peut émettre un certificat qu'un vérificateur $ v_r $ peut vérifier en temps polynomial. Jusqu'à présent, pas de problème. Le complément de ce problème ( $ \ overline {subst-ligne} $ ) est dans $ CONP $ ce qui signifie que Nous ne savons pas s'il y a un certificat (c.-à-d. polynôme) pour décider de la langue. Si un tel certificat n'existe pas, alors $ n \ neq conique $ et donc $ p \ neq np $ . Ce que je ne comprends pas, c'est ceci:

Si j'ai (par exemple) un jeu $ S $ d'entiers et le nombre $ 0 $ comme une entrée et je demande: Prouvez-moi que $ \ Forall s \ in s \ space \ espace \ lnot Subum $ , c'est-à-dire $ \ Nexists $ Un sous-ensemble de $ S $ telle que la somme de son élément donne $ 0 $ Ceci est $ \ Overline {Subsum} $ , le complément du problème du sous-ensemble). Comment existe un certificat pour ce problème dont la vérification est dans $ p $ ? Je veux dire, j'ai besoin de le prouver pour tout le sous-ensemble afin que l'espace de recherche soit le powerset de $ s $ . Si $ | S |= N $ Alors $ \ MATHCAL {| P (S) |}= 2 ^ N $ < / span>. Donc, si le prouveur, par exemple, produire une 2 $ ^ {n / 3} $ certificat, cela signifie que je laisse systématiquement la sortie 2 ^ {\ frac {2} {3} n} $ sous-ensembles. Ce que je ne comprends pas complètement et pour quoi j'ai besoin de clarification, c'est pourquoi cet argument n'est pas accepté comme preuve que $ NP $ n'est pas fermé sous complément.

Answer 1

La preuve fait que Bot doit être un sous-ensemble.Il s'agira peut-être d'un autre indicateur que l'ensemble donné a un certain strict l'empêchant d'être un exemple positif du problème des sous-sols.Un bon exemple avec un certificat non trivial est la programmation linéaire.Les programmes linéaires admettent à la fois un certificat positif et négatif (pour la question de savoir si l'optimal peut être plus petit / supérieur à une valeur K).L'instance positive est bien sûr une affectation de la variable.Le négatif est cependant donné par le lemme de Faraks et la faible dualité.

Un bon exercice pour vous est de rechercher des programmes linéaires, de la faible dualité et de Farkas Lemma :)