Implications de l'improvisibilité de

22

Je lisais " Est-ce que P par rapport à NP est officiellement indépendant? ", Mais je suis resté perplexe.

Il est largement admis dans la théorie de la complexité que . Ma question est de savoir si ce n'est pas prouvable (disons dans ). (Supposons que nous découvrions seulement que est indépendant de mais aucune autre information sur la façon dont cela est prouvé.)PNPZFCPNPZFC

Quelles seront les implications de cette déclaration? Plus précisement,

dureté

En supposant que capture les algorithmes efficaces ( thèse de Cobham – Edmonds ) etPPNP , nous prouvons les résultats de pour impliquer qu'ils sont au-delà de la portée actuelle de nos algorithmes efficaces. Si nous prouvons la séparation, N P - h a r d n e s s signifie qu'il n'y a pas d' algorithme polynomial. Mais qu'est-ce qu'un N P - h a r d n eNP-hardnessNP-hardness signifie-t-il si la séparation n'est pas prouvable? Qu'adviendra-t-il de ces résultats?NP-hardness

algorithmes efficaces

L'improvabilité de la séparation signifie-t-elle que nous devons changer notre définition d'algorithmes efficaces?

karthik
la source
13
La première chose que vous devez demander est: formellement indépendante de quoi? En logique mathématique, il existe de nombreux ensembles d'axiomes que les gens ont pris en considération. La valeur par défaut est ZFC, ou la théorie des ensembles de Zermelo-Fraenkel avec l'Axiom of Choice. Ce que signifie être indépendant de ZFC, c'est que ni P = NP ni P! = NP ne peuvent être prouvés à partir de ces axiomes.
Peter Shor
2
Si vous voulez savoir à quoi ressemble une preuve pour une déclaration de la forme «si X est indépendant du système axiomatique Y», pourquoi ne lisez-vous pas simplement quelques exemples? L'indépendance de l'Axiom of Choice par rapport à la théorie des ensembles de Zermelo-Fraenkel est un exemple célèbre. J'ai voté pour fermer car ce n'est pas une vraie question par erreur, mais je voulais voter pour fermer comme hors sujet.
Tsuyoshi Ito
15
Avez-vous lu le très bon article de Scott Aaronson disponible gratuitement? "Est-ce que P par rapport à NP est officiellement indépendant?" ( scottaaronson.com/papers/pnp.pdf )
Marzio De Biasi
2
La question "si X est prouvé indépendant de ZFC, et que nous avons quelques théorèmes de la forme X Y, qu'advient-il de ces théorèmes?" semble bien posée, et c'est la question que je crois que le PO pose. La réponse semble être: dans certains systèmes d'axiomes, tels que ZFC + X, nous avons alors Y tenant, tandis que dans ZFC + ¬ X nous n'avons aucune information sur Y. En tant que tels, ces théorèmes conditionnels auraient encore une certaine valeur. En fait, ils auraient plus de valeur dans cette situation que si ¬ X s'avérait être un théorème. ¬¬
András Salamon
2
L'improvabilité ZFC de P vs NP aurait probablement beaucoup plus d'implication pour la théorie des ensembles que pour la théorie de la complexité.
David Harris

Réponses:

18

Votre question pourrait être mieux formulée, "Comment la théorie de la complexité serait-elle affectée par la découverte d'une preuve que P = NP est formellement indépendant d'un système axiomatique fort?"

Il est un peu difficile de répondre à cette question dans l'abstrait, c'est-à-dire en l'absence de voir les détails de la preuve. Comme Aaronson le mentionne dans son article, prouver l'indépendance de P = NP nécessiterait des idées radicalement nouvelles, pas seulement sur la théorie de la complexité, mais sur la façon de prouver les déclarations d'indépendance. Comment pouvons-nous prédire les conséquences d'une percée radicale dont nous ne pouvons même pas deviner la forme actuellement?

Pourtant, nous pouvons faire quelques observations. Dans la foulée de la preuve de l'indépendance de l'hypothèse du continuum par rapport à ZFC (et plus tard par rapport à ZFC + grands cardinaux), un nombre important de personnes sont arrivées au point de vue que l'hypothèse du continuum n'est ni vraie ni fausse . Nous pourrions nous demander si les gens arriveront de la même manière à la conclusion que P = NP n'est "ni vrai ni faux" à la suite d'une preuve d'indépendance (pour les besoins de l'argument, supposons que P = NP soit prouvé indépendant de ZFC + tout grand axiome cardinal). Ma supposition ne l'est pas. Aaronson dit essentiellement qu'il ne le ferait pas. Le deuxième théorème d'incomplétude de Goedel n'a conduit personne à ma connaissance à dire que "ZFC est cohérent" n'est ni vrai ni faux., et la plupart des gens ont une forte intuition selon laquelle les déclarations arithmétiques - ou du moins les déclarations arithmétiques aussi simples que «P = NP» - doivent être vraies ou fausses. Une preuve d'indépendance serait simplement interprétée comme disant que nous n'avons aucun moyen de déterminer lequel de P = NP et P NP est le cas.

On peut également se demander si les gens interpréteraient cet état de choses comme nous disant qu'il y a quelque chose de "mal" dans nos définitions de P et NP. Peut-être devrions-nous alors refaire les fondements de la théorie de la complexité avec de nouvelles définitions plus faciles à travailler? À ce stade, je pense que nous sommes dans le domaine de la spéculation sauvage et infructueuse, où nous essayons de traverser des ponts auxquels nous ne sommes pas parvenus et d'essayer de réparer des choses qui ne sont pas encore rompues. De plus, il n'est même pas clair que quoi que ce soitêtre "cassé" dans ce scénario. Les théoriciens des ensembles sont parfaitement satisfaits de l'hypothèse que les grands axiomes cardinaux qu'ils jugent utiles. De même, les théoriciens de la complexité pourraient également, dans ce monde futur hypothétique, être parfaitement heureux en supposant que tous les axiomes de séparation qu'ils croient sont vrais, même s'ils sont prouvables non prouvables.

Bref, rien ne découle logiquement d'une preuve d'indépendance de P = NP. Le visage de la théorie de la complexité pourrait changer radicalement à la lumière d'une percée aussi fantastique, mais nous devrons simplement attendre et voir à quoi ressemble cette percée.

Timothy Chow
la source
3
@vzn: Vos exemples ne sont pas seulement "sans doute" arithmétiques; ils sont incontestablement arithmétiques. Mais je ne sais pas quel est votre point. Prenez une équation diophantienne avec la propriété que " E n'a pas de solutions" est indécidable dans ZFC. Mon point est que tous ceux que je connais croient que E a des solutions ou non, et que nous ne pouvons tout simplement pas le prouver dans un sens ou dans l'autre. Croyez-vous qu'il n'y a aucun fait sur la question de savoir si E a des solutions - que E n'a pas ou n'a pas de solutions? EEEEE
Timothy Chow
4
@vzn: Je pense que vous manquez complètement le point. La question n'est pas de savoir si une déclaration particulière est indécidable , mais si elle n'est ni vraie ni fausse . Les deux concepts sont entièrement distincts. Diriez-vous, par exemple, que ZFC n'est ni cohérent ni incohérent? Tout le monde (autrement) que je connais pense que le ZFC est cohérent ou non, même si nous n'avons aucun moyen de déterminer quel est le cas.
Timothy Chow
3
"cela ressemble à de la religion pour moi et non à des mathématiques" - Bienvenue dans la métamathématique. Une façon peut-être moins répréhensible de dire "X n'est ni vrai ni faux" est que nous n'avons a priori aucune raison de préférer un système axiomatique dans lequel X est vrai à un système axiomatique dans lequel X est faux. Nous avons un modèle standard (presque) universellement accepté d'arithmétique; en tant que convention sociale, nous acceptons les affirmations arithmétiques qui tiennent dans ce modèle comme étant réellement, réellement vraies. On ne peut pas en dire autant de la théorie des ensembles.
Jeffε
2
Voir aussi consc.net/notes/continuum.html et mathoverflow.net/questions/14338/… - Le mélange personnel de chaque mathématicien entre formalisme, platonisme et intuitionisme est essentiellement une conviction religieuse.
Jeffε
2
@vzn: Vous manquez toujours le point. Même si nous vous accordons vos croyances religieuses personnelles, tout ce que vous dites, c'est que vous ne vous joindriez pas à Aaronson et au reste du monde pour déclarer que les phrases arithmétiques sont vraies ou fausses. Nous convenons tous qu'il n'y a aucun moyen de dire, sous la forme d'une déclaration, si c'est indécidable , mais ce n'est pas la prétention. La demande est que presque tout le monde , sauf que vous n'avez de fortes intuitions que les déclarations sont arithmétiques vraies ou fausses . Ce n'est pas parce que vous ne partagez pas cette conviction que d'autres ne l'ont pas.
Timothy Chow
11

C'est une question valable, même si peut-être un peu malheureusement formulée. La meilleure réponse que je puisse donner est cette référence:

Scott Aaronson: Est-ce que P contre NP est officiellement indépendant . Bulletin de l'Association européenne d'informatique théorique, 2003, vol. 81, pages 109-136.

Résumé: Il s'agit d'une enquête sur la question du titre, écrite pour les personnes qui (comme l'auteur) voient la logique comme interdite, ésotérique et éloignée de leurs préoccupations habituelles. Commençant par un cours intensif sur la théorie des ensembles de Zermelo Fraenkel, il traite de l'indépendance d'Oracle; preuves naturelles; les résultats d'indépendance de Razborov, Raz, DeMillo-Lipton, Sazanov et autres; et les obstacles à la preuve de P vs NP indépendamment des théories logiques fortes. Il se termine par quelques réflexions philosophiques sur le moment où il faut s'attendre à ce qu'une question mathématique ait une réponse définie.

Andrej Bauer
la source
2
Euh, j'ai totalement raté le fait que le document d'Aaronson était déjà mentionné dans les commentaires. Mes excuses.
Andrej Bauer
7

[ZFC][1]. Cela signifie simplement que la théorie ne peut prouver ni l'énoncé ni sa négation. Cela ne signifie pas que l'énoncé n'a pas de valeur de vérité, cela ne signifie pas que nous ne pouvons pas connaître la valeur de vérité de l'énoncé, nous pourrions être en mesure d'ajouter de nouveaux axiomes raisonnables qui rendront la théorie suffisamment solide pour pouvoir pour prouver les déclarations ou sa négation. À la fin, la prouvabilité dans une théorie est un concept abstrait formel. Elle n'est liée à notre expérience du monde réel qu'en tant que modèle.

P

Σ1Π1Topology via Logic ", 1996.)

PNPΣ2et recherchez les messages sur la liste de diffusion FOM .

Kaveh
la source
4

Comme prouvé dans cet article:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf

Si P! = NP peut être montré indépendant de Peano Arithmetic, alors NP a des limites supérieures de temps déterministes extrêmement proches du polynôme. En particulier, dans un tel cas, il existe un algorithme DTIME (n ^ 1og * (n)) qui calcule correctement SAT sur une infinité d'intervalles énormes de longueurs d'entrée.

Un vital
la source
0

Juste quelques réflexions à ce sujet. N'hésitez pas à critiquer.

Soit Q = [ne peut pas prouver (P = NP) et ne peut pas prouver (P / = NP)]. Supposons Q pour une contradiction. Je supposerai également que toutes les découvertes connues sur P vs NP sont encore viables. En particulier, tous les problèmes NP sont équivalents en ce sens que si vous pouvez résoudre l'un d'eux en temps polynomial, vous pouvez résoudre tous les autres en temps polynomial. Soit donc W un problème complet NP; W représente également tous les problèmes de NP. A cause de Q, on ne peut pas obtenir un algotithme A pour résoudre W en temps polynomial. Sinon, nous avons la preuve que P = NP, ce qui contredit Q (1) (*). Notez que tous les algorithmes sont calculables par définition. Donc, dire que A ne peut pas exister implique qu'il n'y a aucun moyen de calculer W en temps polynomial. Mais cela contredit Q (2). Il nous reste à rejeter (1) ou à rejeter (2). Les deux cas conduisent à une condradiction. Ainsi Q est une contradiction,

(*) Vous pourriez dire: "Aha! A peut exister, mais nous ne pouvons tout simplement pas le trouver". Eh bien, si A existait, nous pouvons énumérer tous les programmes pour trouver A en énumérant des programmes plus petits aux programmes plus grands, en commençant par le programme vide. A doit être fini car c'est un algorithme, donc si A existe, alors le programme d'énumération pour le trouver doit se terminer.

Thomas Eding
la source
1
@Victor: Bon point. J'imagine que si A existe, alors on peut simplement analyser chaque programme énuméré pour voir s'il résout effectivement un problème NP complet en temps polynomial. Je crois que puisque l'on travaille avec un jeu d'instructions fini (donné par un ordinateur universel), A peut être identifié. Mais je ne suis pas un expert.
Thomas Eding
1
Le problème est que si Q est vrai, alors nous tomberions dans un cas où personne, aussi intelligent soit-il, ne pourrait prouver qu'un algorithme particulier X généré par l'énumérateur résout P = NP, même s'il le fait. C'est-à-dire dans ce cas, un algorithme pour déterminer si P = NP existe et peut être trouvé, mais il est impossible de prouver analytiquement son exactitude. En outre, une déclaration comme "l'algorithme X résout-il le problème P = NP?" semble très indécidible.
Victor Stafusa
1
Aussi ... Si A existe, alors Soit N la taille de A. Soit T l'ensemble de tous les programmes de taille <= N. On peut exécuter simultanément W sur tous les A 'dans T. Comme chaque A' se termine, exécuter la sortie O via un programme qui vérifie si O résout W. (Notez que toute soi-disant «solution» à un problème NP complet peut être vérifiée en temps polynomial.) Si O est une réponse correcte, arrêtez tous les autres ordinateurs et retourner O. Gardez à l'esprit que tous les A 'ne doivent pas se terminer car A est l'un d'entre eux et produira un O correct en temps polynomial. Ainsi, il n'est même pas nécessaire de prouver que A résout P = NP. N existe par définition.
Thomas Eding
1
Dans votre section (*): "A doit être fini car c'est un algorithme, donc si A existe, alors le programme d'énumération pour le trouver doit se terminer.". Cela signifie que l'énumérateur devrait en quelque sorte être capable de déterminer si le programme qu'il vient de générer résout un problème NP-complet en temps polynomial, ce qui est certainement indécidible (d'autant plus que nous supposons Q ici), et donc l'énumérateur ne s'arrêtera jamais .
Victor Stafusa
3
"P = NP est indépendant de ZFC" n'est pas la même chose que "nous ne pouvons pas trouver d'algorithme pour résoudre tout problème dans NP en temps polynomial déterministe", comme l'a souligné Victor. Les définitions précises de ces classes sont assez importantes lorsqu'il s'agit de notions telles que l'indépendance par rapport à une théorie.
András Salamon