Pourquoi le deuxième théorème d'incomplétude de Godel n'exclut-il pas une preuve formalisable de P! = NP?

Je suis sûr qu'il doit y avoir quelque chose qui ne va pas dans le raisonnement suivant, car sinon beaucoup de recherches P vs NP seraient réduites mais je ne peux pas déterminer mon erreur:

Pour tout entier fixe définissez $k>0$

B_{k} := {⟨ φ ⟩ | φ is a wff of ZF and has a proof of length \leq k {| φ |}^{k}}

$B_k := \{ \langle \varphi \rangle | \; \varphi \; \text{is a wff of ZF and has a proof of length} \; \leq k{|\varphi|}^k \; \}$

Maintenant pour tout , le langage est en NP car une preuve valide pour de longueur peut être un témoin NP vérifié par un correcteur d'épreuves automatisé en temps polynomial. De plus, pour suffisamment grand , est NP-complet puisque SAT se réduit à lui: c'est-à-dire que pour une instance de SAT faire un wff correspondant de ZF utilisant des quantificateurs existentiels. Ensuite, une affectation de vérité satisfaisante de peut être transformée en une preuve formelle de de polynôme de longueur dansdepuis une affectation de vérité de $k$ $B_k$ $\varphi$ $\leq k{|\varphi|}^k$ $k$ $B_k$ $\phi$ $\varphi$ $\phi$ $\varphi$ $|\varphi|$ $\phi$ est linéaire dans. $|\phi|$

Maintenant, si ZF est incohérent, cela signifie qu'il existe une instruction formelle telle que et ont des preuves dans ZF. Comme on le sait, toute autre instruction peut alors être dérivée de la conjonction contradictoire (c'est-à-dire en suivant le chemin: $\sigma$ $\sigma$ $\neg \sigma$ $\tau$ $\langle \sigma \wedge \neg \sigma \rangle$

⟨ σ \land \neg σ ⟩ ⟹ tous les deux σ et \neg σ sont vrai ⟹ ⟨ \neg τ \to σ ⟩ est vrai (car indépendamment de τ l'implication est valable puisque σ est vrai) ⟹ ⟨ \neg σ \to τ ⟩ (par contraposition et double négation) ⟹ τ est vrai (par modus ponens avec \neg σ)

$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \; \sigma \; \text{and} \; \neg \sigma \; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \; \text{is true (since regardless of} \; \tau \; \text{the implication is valid since} \; \sigma \; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \; \text{(by contraposition and double negation)} \implies \tau \; \text{ is true (by modus ponens with} \; \neg \sigma \, )$

). Ainsi, si ZF est incohérent, alors chaque instruction a un polynôme de preuve (il me semble même juste linéaire) dans. $\varphi$ $|\varphi|$

Soit pour un suffisamment grand mentionné ci-dessus pour permettre à d'être NP-complet. Ensuite, si ZF est incohérent, il n'y a qu'un nombre fini de tels que car la tolérance de longueur de preuve polynomiale à haut degré de est suffisante pour couvrir les preuves courtes garanties de wffs de longueur suffisante. Cela implique que est décidable en temps polynomial qui par sa complétude NP implique que P = NP. Si nous reformulons cette chaîne de raisonnement en termes de contrapositifs, si P! = NP alors ZF n'est pas incohérent (c'est-à-dire qu'il est cohérent). $B:=B_k$ $k$ $B$ $\varphi$ $\langle \varphi \rangle \notin B$ $B$ $B$

Par conséquent, si nous avons une preuve formelle de P! = NP, alors nous avons une preuve formelle de la cohérence de ZF. Mais selon le second théorème d'incomplétude de Godel, cela implique que ZF est incohérent, ce qui à son tour obtient P = NP comme indiqué ci-dessus (ainsi que le théorème de tout théorème nié).

Ce n'est pas exactement une preuve que P vs NP est indépendant de ZF. Il se pourrait que ZF soit cohérent et que P = NP ou que P! = NP puisse être prouvé par des techniques non formalisables dans ZF. Cependant, il présente une autre formidable barrière à la résolution de P vs NP.

complexity-theory np-complete logic p-vs-np Ari
la source

Réponses:

Il semble y avoir une faille à laquelle Arno fait allusion dans sa réponse. Alors que la réduction semble assez anodine (et est en effet un exercice de manuel comme l'a souligné Ariel dans son commentaire), elle suppose implicitement la cohérence de ZF. Sinon, si ZF est incohérent, puisque chaque déclaration de ZF aurait alors une preuve, les instances SAT insatisfaisantes ne seraient pas nécessairement mappées vers wffs qui n'ont pas de preuve relativement courte. $SAT \leq B$ $\varphi$

Ainsi, si nous supposons que ZF est cohérent et bien que nous puissions conclure de façon métamathématique que (car étant NP-complet, ne pourrait pas être dans puisque nous supposons ) nous n'aurions pas de déduction formelle de (puisque cela dépend de étant un ensemble NP-complet établi, donc si nous voulons utiliser la réduction ci-dessus, nous devons supposer que ZF est cohérent, ce qui ne peut pas être formellement affirmé par le deuxième théorème d'incomplétude de Godel). Cet argument ne peut donc suggérer aucune implication nécessaire de . $ZF \vdash P \neq NP$ $B \notin P$ $B$ $P$ $P \neq NP$ $ZF \vdash B \notin P$ $B$ $ZF \vdash P \neq NP$

Ari
la source

Bon travail! cela semble être le problème.

Ariel

Le problème réside dans votre affirmation que pour un suffisamment grand , le langage est NP-complet. Dans la réduction que vous proposez, vous affirmez simplement que toute instance SAT satisfaisante correspond à une formule ZF avec une preuve "courte". Cependant, vous devez également faire valoir que chaque fois que la formule ZF résultante a une preuve courte, alors l'instance SAT d'origine est satisfaisable. Bien sûr, cela revient à dire que si ZF prouve que l'instance SAT est satisfaisable, alors c'est vraiment le cas - mais ici, nous utilisons la solidité de ZF. $k$ $B_k$

Arno
la source

Vous avez raison en ce que je suppose implicitement la solidité de ZF et la justesse d'un correcteur d'épreuves, mais comment cela affecte-t-il la preuve que est NP-complet? Ce ne sont là que des hypothèses nécessaires pour que le langage présente un quelconque intérêt. Sous ma réduction, seule une instance SAT satisfaisante aura une preuve de n'importe quelle longueur car une insatisfaisante correspond à une déclaration ZF qui est fausse.

B_{k}

$B_k$

B_{k}

$B_k$

Ari

@Ari Les instances SAT non satisfaisantes correspondent à des déclarations ZF qui sont fausses dans votre méta-théorie. Donc, pour que la réduction fonctionne, vous avez besoin que les fausses instructions ZF n'aient pas de preuve ZF.

Arno

L'équivalence est claire, si la formule a une preuve, alors l'instance SAT est satisfiable (ZF est solide, je ne vois pas pourquoi cela devrait être un obstacle ici). Voir cette question pour une preuve de son exhaustivité NP.

Ariel

@Ariel La réponse à cette question est imprécise sur les hypothèses. Il faut nécessairement supposer que ZF est sain. Juste le rappel: "Son" signifie que si une déclaration a une preuve, alors c'est vrai. Si ZF est incohérent, il prouve tout et ne peut donc pas être sain. En particulier, nous voyons que "ZF is sound" n'est pas un théorème de ZF. Si notre méta-théorie prouve que "ZF est solide", alors elle prouve également que "ZF est cohérent", et il n'y a pas de problème. Si cela ne le prouve pas, nous n'avons pas la preuve d'exhaustivité de NP, et il n'y a pas de problème non plus.

Arno

La justesse de la réduction repose en effet sur la cohérence du ZF, mais cela n'a rien à voir avec la solidité. Rappelez-vous que la solidité est définie par rapport à certaines sémantiques, et ZF est solide dans le sens où les déclarations prouvables sont vraies dans tous les modèles, si ZF est incohérent, il est vide de son car il n'a pas de modèles.

Ariel