Prouver P = NP sans instructions mathématiques / programme informatique

Ceci est mon premier article après avoir été un utilisateur passif depuis un certain temps maintenant. Je voudrais poser quelques questions si vous le permettez. Je ne suis pas mathématicien mais ma question concerne le domaine des mathématiques / informatique. En particulier, le problème P vs NP. Je suis conscient que c'est un problème que les professionnels d'élite n'ont pas encore pu résoudre ...

Quoi qu'il en soit, je voudrais demander:

Si une personne qui n'est ni mathématicien ni programmeur devait proposer un organigramme ou une série d'étapes écrites en anglais de base qui fourniraient une solution à l'un des problèmes P vs NP, cela serait-il considéré comme `` prouvant '' que P = NP .. pour réclamer le prix Clays Institute :)? Ou est-ce indispensable pour écrire la solution sous forme de preuves mathématiques / programme informatique?

Je vous remercie.

"Non", vous pouvez utiliser "l'anglais de base".

Si vous réussissiez, vous auriez créé une preuve constructive . Les preuves en mathématiques sont souvent un mélange «d'anglais de base» comme vous l'appelez et de formules mathématiques, mais elles ne doivent pas nécessairement contenir non plus pour être une preuve valide.

Supposons que vous ayez un tel organigramme, ce que vous devez prouver, c'est-à-dire argumenter, c'est que votre algorithme fonctionne pour chaque instance de problème. La façon dont vous le faites dépend entièrement de vous, tant que la preuve est sans ambiguïté et que toutes les prémisses que vous affirmez se sont avérées vraies.

Cela fait, vous avez une preuve mathématique entre les mains. Donc, vraiment, j'aurais dû dire " Oui " au début, vous avez besoin d'une preuve mathématique .

Une machine de Turing, il faut le rappeler, est une sorte de diagramme. Il en est de même de la structure d'un programme informatique en général. Donc, transformer "un organigramme" en une réponse formelle au problème devrait être assez facile, si cela fonctionnait réellement. En effet, si l'on commençait par une réponse terriblement formelle à P versus NP , la plupart des informaticiens essaieraient d'en trouver une formulation qui se rapprocherait le plus possible d'une description en anglais simple afin d'avoir une compréhension aussi forte de la solution que possible.

Mais il y a un problème fondamental avec le genre de question que vous posez. Qu'est-ce que cela signifie pour quelqu'un qui serait en mesure de résoudre P rapport NP - et en montrant qu'ils sont égaux, rien de moins - de ne pas être en fait un informaticien ou un mathématicien? Peut-être qu'ils ne sont pas employés professionnellement en tant qu'informaticien ou mathématicien, mais ce n'est pas la question s'ils ont les compétences nécessaires pour résoudre ce que certains (Scott Aaronson, par exemple) décrivent comme le problème mathématique le plus important que nous ayons jamais considéré. Si quelqu'un a la formation (ou a même autodidacte) pour s'attaquer avec succès au problème, et aussi pour communiquer clairement la solution aux autresen identifiant les principales sous-routines et leurs rôles dans la résolution, par exemple SAT ou HAMPATH, alors si elles sont employées ou même diplômées, ce n'est pas un détail pertinent; ils sont néanmoins dans ce cas un mathématicien ou un informaticien. Mieux encore s'ils peuvent décrire comment leurs solutions surmontent les obstacles classiques tels que les résultats oracle, tels que les oracles A pour lesquels P ^A ≠ NP ^A (ou l'inverse) en montrant spécifiquement de quelles sortes de structure dans le problème l'algorithme tire parti, ce qui ne serait pas accessible dans le modèle oracle. Le problème, cependant, est que la plupart des gens qui rêvent de résoudre P contre NP en tant qu'amateurs ou étrangerssemblent manquer de compétences en communication pour décrire correctement leur travail, ou (du fait de ne pas avoir suffisamment lu), ils ignorent les résultats qui rendraient leur approche de la résolution du problème vouée à l'échec dès le départ.

Comme pour tous les rêves de gloire de nos jours, il y a un problème fondamental avec le fantasme d'être celui qui résout P contre NP . Le problème est que cela est presque impossible. Pas vraiment impossible, ne vous en faites pas, ou du moins pas nécessairement impossible; presque. En tant que personne brillante d'ambition, il est possible pour quelqu'un de perdre de vue le fait qu'il existe de nombreuses autres personnes brillantes: dont beaucoup ont également pensé au problème; et beaucoup d'entre eux sont plus brillants que soi, même de quelques ordres de grandeur. Et qu'il y a eu des gens si brillants depuis aussi longtemps que le problème existe; et pourtant cela reste non résolu. Oui, il est possible en principe que tout le monde y pense de la mauvaise façon, et ce depuis des décennies. Mais est-cevraiment particulièrement probable? Personne ne devrait s'attendre à être la seule personne capable de repérer la seule erreur de signe que tout le monde fait, car si tout le monde fait cette erreur, il doit y avoir quelque chose dans le problème qui amènera quelqu'un à commettre la même erreur. Ou - dans le cas le plus probable où la raison pour laquelle le problème reste non résolu n'est pasque les gens continuent de faire des erreurs simples ou n'ont pas encore pensé à la seule astuce simple qui dissout le tout - ce qui rend le problème fondamentalement difficile est essentiellement une difficulté objective du problème, et aucun pas de danse intelligent ne permettra de valser simplement avec élégance passé tous les obstacles; que ce qui est requis est une approche qui n'est pas seulement nouvelle, mais assez profonde, identifiant des structures subtiles qu'il n'y avait de bonnes raisons pour personne de les avoir vues auparavant. Le type de structure que l'on est le plus susceptible de repérer en réfléchissant continuellement au problème pendant des années.

Si vous voulez être réaliste sur ce qu'il faudrait pour résoudre le problème P contre NP , vous pouvez le comparer à des percées similaires au cours des dernières décennies, telles que les preuves du théorème à quatre couleurs, le dernier théorème de Fermat, ou le Conjecture de Poincaré. Ils pourraient avoir des preuves plus simples un jour, mais les preuves originales vous emmènent loin dans le désert pour vous mener à la fin (ou dans le cas du théorème des quatre couleurs, l'itinéraire est très long et répétitif). Il n'y a aucune raison particulière de soupçonner que P contre NP sera différent; de sorte que si à la fin il estrésolu par un amateur, les chances sont extrêmement fortes que ce soit par une personne ayant des connaissances de base similaires et une sensibilisation aux techniques d'une personne ayant une formation académique. Tout amateur réaliste qui rêve de résoudre P contre NP ferait bien de garder cela à l'esprit.

Une preuve que P = NP pourrait être acceptée par une revue mathématique, mais elle ne sera jamais acceptée par les professionnels d'élite. La raison en est qu'ils savent que P! = NP (au moins à toutes fins pratiques). Ils savent également qu'il est incroyablement difficile de le prouver, donc même une preuve que P! = NP sera reçue avec une bonne dose de scepticisme par les professionnels de l'élite.

Les professionnels d'élite ont des raisons plus élaborées que le fait que de nombreux esprits brillants ont essayé et échoué à construire un algorithme polynomial pour NP ou à prouver N! = NP. Cependant, ils s'attendent raisonnablement à ce que cet argument soit le plus convaincant pour un profane. Ils ont probablement raison de dire que la référence aux barrières liées aux preuves relativisantes, aux preuves naturelles ou aux preuves algébriantes est rarement convaincante pour un non-expert. Si trop "d'amateurs" essaient de résoudre P vs NP d'une certaine manière (par exemple par résolution logique, ou en le réduisant à un problème de programmation linéaire), alors quelqu'un passera par la douleur (cela prend parfois des années) pour prouver que cet angle d'attaque spécifique est probablement voué à l'échec.

Edit Je suis ravi que cette réponse continue d'attirer des commentaires (négatifs). Permettez-moi donc de remplacer la deuxième partie de la réponse (qui ne semble pas liée à la rétroaction, mais peut distraire du point principal) par la citation suivante de Truth vs Proof :

Nous pourrions rester agnostiques, en disant que nous ne savons tout simplement pas, mais il peut y avoir une telle chose comme trop de scepticisme en science. Par exemple, Scott Aaronson a affirmé un jour que dans d'autres sciences, P! = NP aurait désormais été déclaré loi de la nature. J'ai tendance à être d'accord. Après tout, nous essayons de découvrir la vérité sur la nature du calcul et cette quête n'ira pas plus vite si nous insistons pour rejeter toutes les preuves qui ne sont pas sous la forme de preuves mathématiques des premiers principes.

Ce changement n'a pas pour but de réduire la quantité de commentaires, mais de montrer parfaitement que cette réponse est sérieuse du fait que les experts "savent que P! = NP", même s'ils ne peuvent pas le prouver.

23 nov. 2013 Merci encore pour tous les retours. Pour mémoire, la réponse a maintenant 7 downvotes, 1 upvote et 14 commentaires (8 par moi). En raison de la quantité de commentaires, les références et justifications intéressantes données dans les commentaires sont cachées, j'ai donc décidé d'en ajouter ici:

• Comme Gödel lui-même l'a écrit à von Neumann, si P = NP était vrai "à toutes fins pratiques", alors son théorème d'incomplétude ne serait vrai qu'en théorie, mais effectivement faux en pratique.

• Dans son article de 1971, Stephen Cook ... incapable de produire des contre-exemples pour la procédure Davis-Putnam (résolu par Haken 1985). Aujourd'hui, de nombreuses techniques, résultats et contre-exemples sont disponibles pour "réfuter" les résolveurs NP efficaces proposés. P = NP contredit également la "loi de conservation de la difficulté", la correspondance "qualitative infinitaire <-> quantitative finitaire", ...

• Il y a longtemps, Scott Aaronson a écrit ce commentaire :

  anonyme: Vous prétendez (comme étant un fait!) que 3SAT est un langage en NP qui ne peut pas être calculé en temps polynomial. Mais vous ne pouvez pas le prouver. Est-ce votre méthode scientifique? Oui. Fervent partisan de la science et de la raison, je m'efforce de distinguer clairement entre ce que je peux prouver et ce que je sais simplement vrai.

• Scott est célèbre pour avoir tenté de démontrer ce que cela signifie qu'il "sait" quelque chose, par exemple en misant 200 000 $: scottaaronson.com/blog/?p=458