Sur la prouvabilité de P versus NP

Tout d'abord, ma compréhension du théorème d'incomplétude de Gödel (et de la logique formelle en général) est très naïve, tout comme mes connaissances en informatique théorique (c'est-à-dire qu'un seul cours de troisième cycle est suivi pendant que je suis encore étudiant), donc cette question peut être très naïf.

Pour autant que je puisse trouver, la prouvabilité de P contre NP est un problème ouvert.

Maintenant:

Le premier théorème d'incomplétude de Gödel déclare qu'il peut y avoir des déclarations qui sont vraies mais non prouvables ni réfutables.
Si une solution polynomiale est trouvée pour un problème NP-complet, cela prouve que P = NP.

Supposons donc que P = NP ne soit pas prouvable:
cela signifie qu'aucun exemple de solution polynomiale pour un problème NP-complet ne peut être trouvé (sinon, ce serait une preuve).
Mais si aucun exemple de solution polynomiale pour un problème NP-complet ne peut être trouvé, cela signifie que P = NP est faux (le prouvant, ce qui signifie que l'énoncé est prouvable), ce qui conduit à une contradiction, donc P = NP devrait être prouvable .

Cela ressemble à une preuve de la prouvabilité de P = NP pour moi, mais je pense qu'il est extrêmement probable que cela soit dû à mon manque de compréhension des sujets logiques impliqués. Quelqu'un pourrait-il m'aider à comprendre ce qui ne va pas?

np-hardness proofs p-vs-np Alvaro
la source

Voir le document de Scott Aaronson "Le P par rapport au NP est-il formellement indépendant?"

Marzio De Biasi

Il me semble que vous avez une confusion plus fondamentale sur la façon dont quelque chose peut être vrai mais non démontrable. Veuillez consulter la visite guidée et le centre d'aide pour connaître la portée de ce site. Je pense que cela convient mieux à l' informatique ou aux mathématiques .

Kaveh

ce papier semi-célèbre preuves naturelles par Razborov / Rudich est applicable à cette question

vzn

Vous pouvez également être intéressé par la monographie de Hartmanis "Calculs réalisables et propriétés de complexité prouvables" qui discute essentiellement de ce qui se passe si nous considérons uniquement les problèmes qui sont prouvables en P, en fait en NP, etc.

Joshua Grochow

Réponses:

Si P = NP, il doit y avoir des algorithmes polynomiaux pour les problèmes NP-complets. Cependant, il peut ne pas y avoir d'algorithme qui résout de manière prouvable un problème NP-complet et fonctionne de manière prouvée en temps polynomial.

David Richerby
la source

Donc, ce que vous dites, c'est que la faille est qu'il peut y avoir un exemple de solution polynomiale mais vous ne pourrez peut-être pas prouver qu'elle est polynomiale? Parce qu'alors cela n'est pas considéré dans la preuve par l'exemple, donc je ne vois toujours pas la faille.

Alvaro

Supposons que P = NP mais ce n'est pas prouvable. Cela signifie qu'il existe un algorithme polynomial A pour 3-SAT. Si vous pouviez prouver que A était un algorithme poly-temps pour 3-SAT, cela contredirait l'improvabilité de P = NP. Par conséquent, bien qu'il soit vrai que A s'exécute en temps polynomial et vrai que A résout le 3-SAT, au moins un de ces faits ne peut être prouvé. Pour le dire dans les termes de la question, le fait qu'un algorithme poly-temps pour 3-SAT existe n'implique pas qu'un "peut être trouvé".

David Richerby

Donc, le "Mais si aucun exemple de solution polynomiale pour un problème NP-complet ne peut être trouvé, cela signifie que P = NP est faux" est faux, car il peut y avoir une solution même si elle ne peut pas être trouvée?

Alvaro

C'est correct.

David Richerby

M

$M$

c

$c$

N

$N$

n \geq N

$n \geq N$

n

$n$

M

$M$

n^{c}

$n^c$

$\neq$

Tpecatte
la source