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

13

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.

Raphael
la source
10
Voir cette collection: win.tue.nl/~gwoegi/P-versus-NP.htm . Vous ne voulez pas devenir l'un d'entre eux.
Yuval Filmus
il existe un précédent «faible» possible à cet égard. La diagonalisation et la diagonalisation de Godels peuvent avoir été vaguement basées sur le paradoxe de Richard qui provenait du travail littéraire. mais notez qu'il a fallu des mathématiciens extrêmement avancés pour le convertir en déclarations / propriétés mathématiques légitimes.
vzn
@vzn: la page Wikipédia que vous liez aux dates du paradoxe de Richard à 1905; la diagonalisation remonte à 1891. Le paradoxe de Richard est donc probablement basé sur la diagonalisation, et non l'inverse.
Niel de Beaudrap
@NieldeBeaudrap, vzn: Vos commentaires se transformaient en conversation, je les ai donc déplacés pour discuter , veuillez continuer.
Gilles 'SO- arrête d'être méchant'

Réponses:

16

"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 .

phant0m
la source
14
Ne donnons à personne de faux espoirs ici. Il est extrêmement improbable qu'un profane puisse résoudre vs N P , ou que la solution puisse être exprimée en «anglais ordinaire». Il y a de meilleures choses à faire pour un profane que d'essayer de résoudre les problèmes mathématiques les plus difficiles. PNP
Andrej Bauer
3
@AndrejBauer Bien sûr, je ne voulais pas laisser entendre que c'est probable. Je suppose que vous auriez aimé une réponse proche de celle de Niel . Mais si cela met bien les choses en perspective, cela ne répond pas vraiment à la question qui a été posée.
phant0m
3
Je sais que vous ne vouliez pas dire quelque chose comme ça. Je voulais juste mettre un avertissement explicite, de peur qu'un journaliste ou quelqu'un ne lise ceci et pense que contre N P sera résolu par un critique littéraire. PNP
Andrej Bauer
@ phant0m: je suis curieux. Mon premier paragraphe ne répond-il pas à la vraie question?
Niel de Beaudrap
@NieldeBeaudrap Bien sûr, cela y répond, mais il semble que la conclusion doive être déduite. Sidenote: On pourrait également interpréter la "Indeed"phrase comme expliquant une preuve par des mots, mais elle ne serait pas en soi une preuve. En outre, une machine de turing n'est pas en soi une preuve, à moins qu'une preuve d'exactitude ne soit donnée. En outre, cela implique que la présentation d'une MT sur un organigramme est intrinsèquement supérieure en tant que «preuve», même lorsqu'elle ne l'est pas.
phant0m
19

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 ANP 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.

Niel de Beaudrap
la source
2
Bien que tout ce que vous dites soit vrai, je crains que cet état d'esprit (qui est devenu répandu sur le terrain, peut-être comme mécanisme de protection) ne décourage le seul génie autodidacte qui pourrait résoudre le problème aujourd'hui. Je pense qu'un message plus utile est: allez suivre autant de formation que nécessaire pour convaincre même un seul professionnel, d'abord de lire votre travail, puis de sa validité. Cela peut prendre des années, mais c'est la voie à suivre.
Raphael
6
@Raphael: Je pense qu'en fait ma mentalité est parfaitement adaptée même à la possibilité d'un génie autodidacte. Mon message au génie autodidacte est le suivant: d'une part, ne pas être un universitaire ne signifie pas que vous n'êtes pas un mathématicien --- et que je jugerais une réponse en fonction de sa qualité. Il incombe donc à ce génie autodidacte de s'assurer que la réponse est de qualité et de se méfier des pièges auxquels les amateurs sont souvent la proie.
Niel de Beaudrap
2
Je crains que cet état d'esprit ... ne décourage le seul génie autodidacte qui pourrait résoudre le problème aujourd'hui. - Bien. Il faut rappeler à votre génie autodidacte que la barre est extrêmement haute et que des dizaines (des centaines?) D'autres génies autodidactes ont essayé et échoué à l'atteindre.
JeffE
"Le dernier théorème de Fermat, ou la 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) ". c'est une attente juste / raisonnable par certains mais d'un autre côté, contrairement aux curiosités théoriques arbitraires comme FLT et 4CT, un cas peut être fait une preuve P vs NP pourrait fournir des outils (fondamentaux) pour d'autres séparations de classes de complexité et la théorie de la complexité en général , ou pourrait même être une pierre de rosette ou un chaînon manquant pour une progression ultérieure ..
vzn
@vzn: Je ne suis pas vraiment sûr de ce que vous voulez dire avec cette distinction. Tout simplement parce que P contre NP est important, il n'est pas plus probable qu'il existe une solution simple qui pourrait être trouvée par un amateur intelligent mais non initié.
Niel de Beaudrap
-5

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

Thomas Klimpel
la source
2
Les amateurs ont produit de nombreuses preuves de P = NP ainsi que PNP. Pour cette raison, il est peu probable que les «professionnels d'élite» envisagent sérieusement les efforts des amateurs. Cependant, si une preuve est correcte, elle sera acceptée par les "professionnels d'élite". Le résultat pourrait ne pas être pertinent pour les praticiens du monde réel (en effet, je pense que cela va être le cas), mais les informaticiens théoriques "professionnels" s'en soucieront de toute façon.
Yuval Filmus
7
Personne ne "sait" que P! = NP. Les experts peuvent le croire fermement, mais aucun expert ne le sait (sauf si quelqu'un a une preuve et l'a gardée pour lui-même). Il est possible, bien que peu probable, que P = NP soit vrai. En complément, tout le monde (en particulier les scientifiques) devrait être ouvert à tout, sauf preuve contraire. Dans ce cas, chaque scientifique, quelle que soit sa conviction, est que P! = NP, devrait accepter la possibilité que P = NP soit valable.
George
7
En mathématiques, le problème d'ignorer la preuve et d'avancer aveuglément est que vous pouvez supposer quelque chose qui ne va pas. Cela va faire la quête aller beaucoup plus lent. Les sciences physiques n'ont pas ce problème (sauf pour des cas comme la gravité quantique / théorie des cordes) car elles doivent être d'accord avec l'expérience.
Peter Shor
1
@ThomasKlimpel: Je me souviens d'avoir posté ce commentaire, mais pas où. Étant donné que celui à qui je répondais (à vous?) Se servait simplement de lui comme d'une autorité pour plaider en faveur de l'exactitude du platonisme mathématique, alors que, après quelque considération, je suis arrivé à une position formaliste, le simple fait que Godel avait une opinion différente sans plus l'élaboration est en effet hors de propos. Les arguments techniques ne sont pas gagnés comme le sont les matchs de tennis, avec une réfutation rapide. De même, les réponses convaincantes sont jugées non seulement par leur concision (bien que cela aide) ni par l'autorité, mais par leur mérite technique.
Niel de Beaudrap
3
@ThomasKlimpel Dans d'autres sciences, nous aurions des observations pour étayer l'hypothèse. Dans le cas de PNP, la seule preuve dont nous disposons est un manque de preuves (à savoir le fait que personne n'a été en mesure de proposer un algorithme polynomial pour un problème NP-difficile). Je ne pense pas que d'autres sciences utiliseraient un manque d'observation comme moyen de «prouver» quelque chose; si vous n'avez jamais vu une pomme se détacher de son arbre, comment pouvez-vous prétendre qu'elle tomberait (pas)?
Raphael