Dans quelle mesure serait-il difficile de dire P vs. NP dans un assistant d'épreuve?

Question

GJ Woeginger répertorie 116 preuves non valides du problème P vs. NP .Scott Aaronson a publié " huit panneaux une preuve de P ≠ NP revendiquée est erroné " pour réduire le battage médiatiqueChaque fois que quelqu'un tente de régler P vs. np.Quelques chercheurs même Refuser des papiers de lecture à la protection de la "P VERSUSNP "question .

J'ai 3 questions connexes:

1. Pourquoi les gens n'utilisent pas d'assistants prêtés qui pourraient vérifier si une preuve de P vs. NP est correcte?
2. Quelle est la dureté ou combien d'effort serait-il d'indiquer P vs. NP dans un assistant d'épreuve en premier lieu?
3. existe actuellement un logiciel qui serait au moins en principe capable de vérifier une preuve P vs. NP?

Answer 1

Je vais être en désaccord avec DW. Je pense que cela est possible (bien que difficile) pour un résultat de P vs. NP à indiquer dans un assistant de preuve, et de plus, je ne ferais pas confiance à aucune preuve supposée à moins qu'elles n'étaient formalisées de cette manière, à moins qu'elles ne viennent de Très sources de bonne réputation.

En particulier, aucune des ressources ne sont basées sur la théorie de type, qui constitue une direction très prometteuse pour les assistants prouvés. Coq a été utilisé pour formaliser la preuve du théorème de 4 couleurs entre autres, donc c'est clairement Capable de soulever des mathématiques lourdes.

Pour répondre à vos questions spécifiques:

1. La principale raison est que les proverbes théorèmes ne sont pas largement acceptés dans la communauté mathématique. Les apprendre à s'efforcer et les mathématiciens sont souvent sceptiques des techniques sous-jacentes (théorie de type, calcul constructive, etc.) Mais il y a des domaines dans lesquels des chercheurs de premier plan sont très à l'aise avec des développements importants formalisés dans un assistant prouvé, comme la théorie des catégories, la théorie des langues de programmation, la logique formelle, etc. Je pense donc que je pense qu'il existe autant d'une question culturelle comme une question de faisabilité inhérente .

   L'autre raison est que, jusqu'à présent, la plupart des "épreuves" prétendues ont été par des manivelles, qui ne veulent pas formaliser leur résultat car elle révélera inévitablement les défauts.

2. Il n'est pas du tout difficile d'indiquer P vs. NP dans un assistant d'épreuve. On pourrait utiliser des machines de Turing, mais il serait probablement plus facile de modéliser un langage de programmation complète simple - à l'aide de familles inductives pour modéliser la sémantique de petites étapes et définir le temps d'exécution comme le nombre d'étapes d'un programme. Vous pouvez définir $ p $ comme les langues acceptées par des programmes haltirés dans un nombre polynomial d'étapes et $ np $ comme langues pouvant être vérifiées en polytime avec un certificat de longueur polynomiale.

   EDIT: il s'avère Il existe des techniques existantes < / a> Pour montrer que les algorithmes fonctionnent dans un temps polynomial dans un prouveur théorique. Donc, cela pourrait être utilisé soit pour montrer un algorithme de polytime pour un problème de NP-dur, soit de dériver une contradiction de l'existence d'un tel algorithme.

3. Il y a tons de logiciels capables de vérifier une telle preuve, à condition que la preuve soit écrite à l'aide de ce logiciel . Les deux candidats que je mettais le plus de stock dans sont coq et Lean . CoQ en particulier a été utilisé pour vérifier plusieurs résultats importants en mathématiques.

Answer 2

L'utilisation d'assistants prêtés à cette fin est certainement possible en principe, mais je soupçonne que cela prendrait plus d'efforts que la plupart des gens qui écrivaient de telles preuves seraient intéressés par la mise en place. Cela nécessiterait une quantité substantielle d'effort de l'auteur d'un prétendu la preuve de P vs NP pour formaliser leur preuve.

Traduire une preuve écrite pour les humains dans un format qu'un assistant prouvé peut vérifier était fastidieux et consommer du temps. J'ai vu des estimations d'un jour à une semaine d'efforts par page de la preuve humaine. Ensuite, il faut également formaliser tous les résultats précédents que la preuve s'appuie sur. Lorsque nous examinons les tentatives récentes de prouver P vs NP, ils utilisent généralement beaucoup de machines avancées et de résultats préexistants sophistiqués des papiers antérieurs, qui devraient également être formalisés.

Pour cette raison, je m'attends à ce qu'il serait totalement pratique de formaliser à la fois la nouvelle preuve proposée et les preuves de tous les résultats précédents qu'il dépend, pour les types de preuves prétendues que nous avons vues jusqu'à présent. Comme User21820 souligne , quel serait plus pratique de formaliser uniquement l'énoncé de tous les résultats précédents figurant sur, mais pas leur preuve. Ainsi, au lieu de prouver le théorème $ t $ , nous formaliserions une preuve que $ (x \ terre y \ terres \ CDOTS) \ implique t $ , où $ x, y, \ dotes $ sont les résultats antérieurs que la preuve repose sur. Cela ne permet de vérifier pleinement le résultat de l'exhaustivité du NP, mais si les personnes ont la confiance dans les résultats antérieurs, cela permettrait aux gens de prendre confiance dans le nouveau résultat. Ce serait beaucoup plus réaliste que de formaliser toute la preuve de $ t $ : alors qu'il prendrait des efforts pour formaliser tous les résultats antérieurs $ x, y, \ dotes $ , c'est beaucoup moins que l'effort de formaliser les preuves de ces résultats antérieurs.

Néanmoins, il serait difficile et nécessite une dépense non triviale d'effort pour formaliser une preuve, même avec ce tour.

Vous pouvez consulter les bibliothèques existantes des théorèmes en mathématiques et en informatique officialisées et officiellement vérifiées: voir http://us.métamath.org/ et http://formalalath.org/ et https://www.isa-afp.org/topics.html et http://mizar.org/library/ . Vous remarquerez peut-être que beaucoup de ce qui est officialisé, il s'agit de matériel de premier cycle de base. Nous sommes loin de formaliser tous les théorèmes enseignés à un niveau de premier cycle, sans parler de ceux enseignés au niveau des diplômés, sans parler de nouveaux résultats de recherche.

Pour plus d'arrière-plan, voir https://math.stackexchange.com/q/792010/14578 et https://math.stackexchange.com/q/113316/14578 et Httpts://math.stackexchange.com/q/1767070/14578 et HTTTPS://math.stackeXchange.com/q/2747661/14578 et http://www.ams.org/notices/200811/tx081101370p.pdf .

Answer 3

I can give a direct answer to (2): $P\ne NP$ has been stated in Lean (along with the other main results of Cook's paper, where the conjecture was first described), as part of the Formal Abstracts project.

Answer 4

I believe your question is not that much of a proper theory question, so with your permission I'll give it a not-so-technical answer.

Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?

Because CS theorists rarely (perhaps extremely rarely) write proofs in machine-verifiable form.

How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?

Very hard at least in the "uninteresting" sense that @DW explained; but it could be anywhere from easy to impossible in the "interesting" sense of expressing the concepts in a proof, if it were to exist.

But you know, this will never happen because:

1. Until a proof is found it can't be done anyway
2. You have to know the proof like the back of your hand to convert it into machine-verifiable form.
3. ... and when enough people know the proof, they will either have found a flaw or be satisfied that it's valid and not care about machine-checking it.

Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?

I'm not well-versed enough in proof verification software to comment about what's actually implemented, but it's probably nearly-impossible to answer your question, because - who knows what form such a proof will take? And thus - how would you know, now, if it's expressible in such a way that your proof verifier can process?