Comment ne pas résoudre P = NP?

Il y a beaucoup de tentatives pour prouver soit ou , et naturellement beaucoup de gens réfléchissent à la question, ayant des idées pour prouver la direction dans laquelle ils veulent aller.P ≠ N $\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Je sais qu'il a été prouvé que certaines approches ne fonctionnent pas et que d'autres sont probablement défaillantes. Il semble également y avoir de soi-disant obstacles que de nombreuses tentatives de preuves ne parviennent pas à surmonter.

Nous voulons éviter d’enquêter sur des impasses, alors c’est quoi?

Je dirais que les obstacles les plus connus à la résolution de sont$P=NP$

1. Relativisation (comme mentionné par Ran G.)
2. Les preuves naturelles - sous certaines hypothèses cryptographiques, Rudich et Razborov ont prouvé que nous ne pouvons pas prouver utilisant une classe de preuves appelée preuves naturelles.$P\neq NP$
3. Algèbre - par Scott Aaronson et Avi Wigderson. Ils prouvent que les preuves que algebrize ne peut pas séparer etN $P$$NP$

Un autre scénario que je connais bien est le résultat qu'aucune formulation de LP ne peut résoudre le TSP (cela a été prouvé par Yannakakis pour les LP symétriques et très récemment étendu aux LP en général). Voici un article de blog discutant du résultat.

Remarque: je n'ai pas encore vérifié la réponse avec soin et il manque des parties à écrire. Considérez-le comme un premier brouillon.

Cette réponse s'adresse principalement aux personnes qui ne sont pas des chercheurs en théorie de la complexité ou dans des domaines connexes. Si vous êtes un théoricien de la complexité et que vous avez lu la réponse, veuillez me prévenir si vous remarquez un problème ou si vous avez une idée en vue d'améliorer la réponse.

Où vous pouvez trouver des solutions revendiquées de P vs. NP

• Il y a La page P-contre-NP qui a une liste de ces demandes.
• Les articles prétendant résoudre la question sont régulièrement publiés sur arXiv .

Autres listes sur la façon de ne pas résoudre P vs NP

Lance Fortnow, tu crois donc t'être établi P NP , 2009

Scott Aaronson, Huit signes Une réclamation P - NP prouve que c'est faux , 2010

Polymath page pour le papier de Deolalikar , où la section des lectures supplémentaires contient une belle liste de références sur le problème.

Comment ne pas approcher P vs NP

Permettez-moi de discuter de "comment ne pas aborder P vs NP" non pas dans le sens d'idées qui ne fonctionneront pas, mais dans un sens plus général. P vs. NP est un problème facile à énoncer (voir aussi ma réponse ici ):

NP = P: Pour chaque problème de décision avec un algorithme de vérificateur de temps polynomial, il existe un algorithme de temps polynomial.

ou équivalent

Il existe un algorithme temporel polynomial pour SAT.
SAT peut être remplacé par tout autre problème NP-complet .

.

Souvent, les gens simplifient à l'excès et à la philosophie, et exagèrent l'importance pratique du problème (comme indiqué ci-dessus). Ces déclarations ont souvent pour but de donner une intuition, mais elles ne sauraient en aucun cas se substituer à l'énoncé mathématique du problème.

L'efficacité théorique n'est pas la même chose que la faisabilité dans la pratique.

Permettez-moi d’abord avec des conséquences pratiques exagérées.

I. Il est possible que P = NP mais cela n’aide en pratique à aucun problème!

Disons par exemple que SAT est dans P mais que l'algorithme le plus rapide pour son temps d'exécution est . Cet algorithme n'est d'aucune utilité pratique.$2^{2^{64}} n^{65536} + 2^{2^{128}}$

II. Il est possible que P NP et nous puissions résoudre efficacement les problèmes liés à NP .$\neq$

Disons par exemple que SAT n'est pas dans P mais a un algorithme avec le temps d'exécution .$n^{\lg^*\lg^* n}$

Pour donner une entrée qui donnerait vous devez utiliser plus d'électrons que l'on pense être dans l'univers. Donc, l'exposant est essentiellement .$\lg^* n > 6$$2$

Le point principal ici est que P est un modèle simple abstrait de calcul efficace, la complexité dans le pire des cas est un modèle simple abstrait d'estimation du coût d'un calcul, etc. Tous ces éléments sont des abstractions, mais personne dans la pratique n'envisagerait un algorithme. comme celui de (I) ci-dessus comme un algorithme efficace vraiment. P est un beau modèle abstrait, il a de belles propriétés, il facilite les problèmes techniques et il est utile. Cependant, comme toute abstraction mathématique, elle cache des détails qui, dans la pratique, peuvent nous intéresser. Il existe différents modèles plus raffinés, mais plus le modèle devient compliqué, moins il est agréable de discuter.

En pratique, l’important pour les gens est de calculer une réponse au problème dans les cas où ils tiennent à utiliser une quantité raisonnable de ressources. Il existe des tâches dépendantes et doivent être prises en compte

Essayer de trouver de meilleurs algorithmes pour des instances pratiques de problèmes difficiles à résoudre est une tentative intéressante et utile. Il existe des algorithmes heuristiques de résolution SAT utilisés dans l'industrie et capables de résoudre des instances pratiques de SAT avec des millions de variables. Il y a même un concours international SAT .

(Mais il existe également de petites instances concrètes dans lesquelles tous ces algorithmes échouent et échouent assez mal, nous pouvons en fait prouver que tous les solveurs SAT modernes et ultramodernes prennent un temps exponentiel pour résoudre des instances simples comme le principe de Pigeonhole propositionnel .)

Gardez à l'esprit que l' exactitude et la durée d'exécution des programmes ne peuvent pas être obtenues simplement en exécutant le programme sur des instances . Peu importe combien de fois vous essayez, aucun montant n'est suffisant. Il y a une infinité d'intrants possibles et vous devez montrer l'exactitude et l'efficacité (le temps d'exécution est polynomial) du programme pour chacun d'entre eux. En bref, vous avez besoin d’une preuve mathématique d’exactitude et d’efficacité. Si vous ne savez pas ce qu'est une preuve mathématique, vous devez d'abord apprendre quelques notions de base en mathématiques (lire un manuel de mathématiques / combinatoire / théorie des graphes discrète, il s'agit d'un bon sujet pour en savoir plus sur ce qui est considéré comme une preuve mathématique).

Faites également attention aux autres affirmations sur P vs NP et aux conséquences de ses réponses. De telles revendications sont souvent basées sur des simplifications similaires.

Les théoriciens de la complexité ne se soucient pas vraiment d'une réponse à P vs NP!

J'ai exagéré un peu. Bien sûr, nous nous soucions d’une réponse à P vs. NP. Mais nous nous en soucions dans un contexte. P vs. NP est notre problème phare mais ce n'est pas le but ultime. C'est un problème facile à énoncer, qui fait appel à de nombreuses idées fondamentales. Il est utile pour expliquer le type de questions qui nous intéresse aux personnes qui ne sont pas familières avec le sujet. Mais nous ne cherchons pas une réponse un peu oui / non à la question.

Nous cherchons à mieux comprendre la nature du calcul efficace . Nous pensons que la résolution de la question s’accompagnera d’une telle compréhension et c’est la véritable raison pour laquelle nous nous en soucions. Cela fait partie d'un énorme corpus de recherche. Si vous voulez avoir un aperçu de ce que nous avons déjà, regardez un bon manuel de théorie de la complexité, par exemple Arora et Barak, « Théorie de la complexité: une approche moderne » ( version préliminaire ).

Supposons que quelqu'un dispose d'une preuve complètement formelle chiffrée de P NP et que nous pouvons en vérifier l'exactitude avec un degré de confiance très élevé en sélectionnant et en déchiffrant quelques éléments de la preuve (voir Théorème Zero-Knowledge Proof et PCP ). . Donc, nous pouvons vérifier la réclamation avec une probabilité d'erreur inférieure à celle d'un météore qui frappe notre maison, nous sommes tout à fait sûrs que la preuve est correcte et P = NP, mais nous ne connaissons pas la preuve. Cela ne créera pas beaucoup de satisfaction ou d’excitation pour nous. La preuve formelle elle-même ne sera pas aussi satisfaisante. Ce que nous recherchons n'est pas une preuve formelle, nous cherchons à comprendre.$\neq$

En bref, du point de vue d'un théoricien de la complexité

P vs. NP n'est pas un casse-tête avec une réponse oui / non. Nous cherchons une réponse à P vs. NP car nous pensons que cela nous permettra de mieux comprendre la nature du calcul efficace. Une réponse sans avancée majeure dans notre compréhension n’est pas très intéressante.

Trop souvent, des non-experts ont réclamé des solutions pour P contre NP, et ces réclamations souffrent généralement de problèmes qu’ils n’auraient pas résolus s’ils lisaient simplement un manuel standard sur la théorie de la complexité.

Problèmes courants P = NP

Les affirmations de P = NP semblent être plus courantes. Je pense que ce qui suit est le type le plus commun. Quelqu'un a une idée, écrit un programme et le teste sur quelques instances. Il pense que le temps est polynomial et qu'il résout correctement un problème NP-complet. Comme je l'ai expliqué ci-dessus, aucun test ne montrera P = NP. P = NP nécessite une preuve mathématique , pas seulement un programme qui semble résoudre un problème NP-complet en temps polynomial.

Ces tentatives souffrent généralement de l'un des deux problèmes suivants:

I. l'algorithme n'est pas vraiment polynomial.

II. l'algorithme ne résout pas toutes les instances correctement.

Signes qu'un argument P NP n'est pas correct$\neq$

[à écrire]

Comment vérifier que votre algorithme ne fonctionne pas vraiment

Vous ne pouvez pas montrer que votre algorithme fonctionne correctement en testant. Mais vous pouvez montrer que cela ne fonctionne pas correctement en testant! Voici comment vous pouvez vous assurer que votre algorithme n’est pas correct si vous êtes prêt à travailler.

Commencez par écrire un programme permettant de convertir les instances de SAT (au format CNF standard) en un problème NP-difficile que vous résolvez. La SAT est l’un des problèmes NP-difficiles les plus étudiés et il est généralement facile de passer d’un autre problème à la SAT. Deuxièmement, prenons les exemples avec lesquels les solveurs SAT à la pointe de la technologie ont des difficultés (par exemple, prenons les exemples de la concurrence SAT) et transmettez-les à votre algorithme pour voir comment il fonctionne. Essayez des instances dures connues comme le principe de pigeonhole propositionnel (et ne trichez pas en les codant en tant que cas spéciaux), des instances cryptographiques (comme les défis d'affacturage RSA ), des instances aléatoires k-SAT près du seuil , etc.

De même, vous pouvez vérifier que votre algorithme n'est pas efficace. Par exemple, si vous pensez que le temps d'exécution de votre algorithme n'est pas mais qu'il faut des jours pour résoudre une instance de disons de taille 1000. Corrigez la limite supérieure polynomiale de temps d'exécution que vous pensez que votre algorithme a. Prenez les instances et estimez le temps que votre algorithme prendra pour les résoudre et vérifiez si elles correspondent à vos estimations.$10 n^2$

Comment vérifier votre idée algorithmique P = NP ne peut pas fonctionner

Si vous faites cela, vous serez à peu près sûr que votre algorithme ne fonctionnera pas (s'il fonctionne mieux que les solveurs SAT à la pointe de la technologie, participez au prochain concours et de nombreuses personnes seraient intéressées par l'étude de votre algorithme et de vos idées).

Maintenant, vous savez que cela ne fonctionne pas vraiment, mais cela ne suffit pas. Tu veux savoir pourquoi,

la raison pour laquelle mon algorithme ne fonctionne pas est un petit problème qui peut être corrigé ou existe-t-il une raison fondamentale pour laquelle il ne peut pas fonctionner?

Parfois, le problème de l'algorithme est simple et on peut identifier conceptuellement ce qui ne va pas. Le meilleur résultat est que vous comprenez la raison pour laquelle votre idée ne peut pas fonctionner. Souvent, ce n'est pas le cas, votre idée ne fonctionne pas mais vous ne pouvez pas comprendre pourquoi. Dans ce cas, gardez à l'esprit:

Comprendre pourquoi une idée ne peut pas fonctionner peut être plus difficile que de résoudre P vs NP!

Si vous parvenez à formaliser suffisamment votre idée, vous pourrez peut-être prouver que certaines idées sont limitées (par exemple, certains résultats indiquent qu'une formalisation particulière de l'algorithme glouton ne peut pas résoudre les problèmes NP-complets). Cependant, c'est encore plus difficile, et vous n'avez pas beaucoup de chance si vous n'avez pas lu un manuel de théorie de la complexité standard.

Parfois, il n’ya même pas une idée conceptuelle claire de la raison pour laquelle l’algorithme devrait fonctionner, c’est-à-dire qu’il est basé sur des heuristiques mal comprises . Si vous n'avez pas une idée conceptuelle claire de la raison pour laquelle votre algorithme devrait fonctionner, vous n'aurez peut-être pas beaucoup de chance de comprendre pourquoi il ne fonctionne pas!

Problèmes courants liés aux revendications de P NP$\neq$

Bien que la plupart des experts pensent que P NP est plus probable que P = NP, de telles affirmations semblent moins fréquentes. La raison en est que la démonstration des limites inférieures semble être une tâche plus ardue que la conception d’algorithmes (mais souvent, prouver que les limites inférieures et les limites supérieures sont intrinsèquement liées ).$\neq$

Problème 1: l'auteur ne connaît pas la définition de P et NP ou, pire encore, ne comprend pas ce qu'est une preuve mathématique. Parce que l'auteur manque de formation mathématique de base, il ne comprend pas quand on lui dit que ce qu'il présente n'est pas une preuve (par exemple, les étapes ne suivent pas les précédentes).

Numéro 2: l'auteur confond "on ne sait pas comment" avec "l'impossibilité mathématique". Par exemple, ils font diverses hypothèses injustifiées et lorsqu'on leur demande "pourquoi cette affirmation est vraie?" ils répondent "comment cela peut-il être faux?". L’un des plus courants est de supposer que tout programme qui résout le problème doit passer par des étapes particulières, par exemple, il doit calculer des valeurs intermédiaires particulières, car il ne peut penser à une autre façon de résoudre le problème.

[à compléter]

Signes qu'un argument P NP n'est pas correct$\neq$

[à écrire]

Comment vérifier votre idée de NP P ne peut pas fonctionner$\neq$

Si une revendication ne souffre pas de ces problèmes fondamentaux, son rejet devient plus difficile. Au premier niveau, on peut trouver une étape incorrecte dans l'argument. La réponse typique de l'auteur est que je peux résoudre ce problème et que cela peut continuer. Comme pour les solutions P = NP, il est souvent très difficile de trouver un problème fondamental avec une idée qui peut montrer qu’elle ne peut pas fonctionner, en particulier lorsque l’idée elle-même est informelle.

Dans le meilleur des cas, si nous pouvons formaliser l’idée et identifier l’obstacle qui montre que l’idée ne peut pas fonctionner, nous avons prouvé un nouveau résultat de barrière (c’est ainsi que les tentatives pour prouver que P NP utilise des limites inférieures du circuit mènent à la barrière Natural Proofs ).$\neq$

La technique la plus courante qui ne peut pas être utilisée est la relativisation , c’est-à-dire l’utilisation d’un TM avec accès Oracle.

L’impossibilité découle d’un article de Theodore Baker, John Gill, Robert Solovay qui montrent l’existence de deux oracles (langues), et tels que et .B P A = NP A P B ≠ NP $A$$B$$\text{P}^A = \text{NP}^A$$\text{P}^B \ne \text{NP}^B$

Ainsi, si on peut relativiser une preuve pour, par exemple, , cela signifierait que pour tous les oracles , ce qui contredit l'existence d' .O P O ≠ NP O$\text{P}\ne \text{NP}$$O$$\text{P}^O \ne \text{NP}^O$$A$

Cela signifie notamment que la diagonalisation ne peut pas être utilisée pour prouver car ces preuves peuvent être relativisées (voir par exemple ces notes de cours) .$\text{P} \stackrel{?}{=} \text{NP}$

Je suggère de lire ce billet de blog de Lance Fortnow :

1. Donc, vous pensez que vous avez réglé P verus NP Vous avez tort. Comprenez-le. Parfois, vous pouvez toujours récupérer quelque chose d’intéressant dans votre preuve imparfaite.
2. Vous pensez que la preuve est correcte. Votre croyance est incorrecte. Retournez à l'étape 1.
3. Faites-vous des hypothèses ou des raccourcis, même apparemment petits et évidents? Utilisez-vous des mots tels que "clairement", "évidemment", "facile à voir", "devrait", "doit" ou "probablement"? Vous prétendez régler peut-être la question la plus importante de toutes les mathématiques. Vous n'obtenez pas de suppositions. Retournez à l'étape 1.
4. Comprenez-vous vraiment le problème P versus NP? Pour montrer P ≠ NP, vous devez trouver une langue L dans NP telle que pour chaque k et chaque machine M exécutée dans le temps (n = longueur d'entrée), M ne calcule pas correctement. L est un ensemble de chaînes. Rien d'autre. L ne peut pas dépendre de M ou k. M peut être n'importe quel programme traitant des chaînes de bits. M peut agir complètement différemment de ce que vous avez défini dans la définition de L. Revenez à l’étape 1.$n^k$
5. Vous soumettez votre article à une archive en ligne. Peut-être que certaines personnes vous diront ce qui manque ou ce qui ne va pas dans votre papier. Cela devrait vous amener à passer à l’étape 1. Mais au lieu de cela, vous apportez quelques modifications insignifiantes à votre papier et à sa publication.
6. Finalement, les gens ignorent votre papier. Vous vous demandez pourquoi vous ne recevez pas la gloire et la fortune.
7. Vous soumettez votre article à un journal.
8. Le papier est rejeté. Si vous êtes intelligent, vous retournerez à l’étape 1. Mais si vous étiez intelligent, vous n’auriez jamais atteint l’étape 7.
9. Vous vous plaignez à l'éditeur soit que l'éditeur ne comprend pas la preuve, soit qu'elle est facilement corrigée. Vous êtes choqué qu'un éditeur ou un journal respectable traite votre article de cette façon.
10. Vous soumettez à nouveau le document, faites appel, essayez d'autres journaux, en vain.
11. Vous êtes convaincu que "l’établissement" supprime volontairement votre document, car notre domaine deviendrait beaucoup moins intéressant si nous réglions le problème P / NP, nous devons donc le garder ouvert à tout prix.
12. Si je vous disais le contraire, vous me croiriez?

C’est un peu obscur / profond / difficile / angle interne / référence / torsion concernant les approches via des circuits datant des années 1980 qui m’avait été signalé il y a des années par Luca Trevisan ailleurs dans le cyberespace, et réitéré par Stasys Jukna, auteur d’un excellent référence proche du sujet, Complexité des fonctions booléennes: avancées et frontières (Algorithms and Combinatorics, Vol. 27 ).

On peut voir une tendance antérieure dans certaines réflexions de Razborov qui a finalement abouti au document Natural Proofs (appelé "naturalisation"). La référence [273] est très technique et difficile et ne semble pas être citée, construite / développée, ou beaucoup réitérée par des papiers / livres ultérieurs, bien que les preuves naturelles puissent être considérées comme une large généralisation ultérieure. l'extrait est de John E Savages excellente référence Models of Computation p457

$\Omega(n^2)$$n$

[270] AA Razborov, «Limites inférieures de la complexité monotone de certaines fonctions booléennes», Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801 (en russe); Traduction anglaise en mathématiques soviétiques. Dokl. 31 (1985), 354–357

[271] AA Razborov, «Limite inférieure de la complexité du réseau monotone du permanent logique», Mat. Zametki 37 (1985), 887 à 900 (en russe); Traduction anglaise en maths. Notes 37 (6) (1985), 485–493.

[273] AA Razborov, «Sur la méthode des approximations», Proc. 21ème Ann. ACM Symp. Théorie de l'informatique (1989), 167–176.