Pourquoi la plupart des scientifiques pensent que P ? NP?

Question

Je lis que la plupart des scientifiques ne croient pas que P = NP. Il est peut-être subjectif, mais peut vous simplifier pourquoi pas? Je ne suis pas assez informé pour avoir une opinion mais je voudrais connaître les définitions et quelques explications pourquoi croire l'un ou l'autre cas « assez simple », par exemple pourquoi croient même qu'il peut être prouvé?

Answer 1

Un problème NP-complet peut être transformé en un autre problème NP-complet. Il y a une abondance de problèmes NP-complets connus, en fait, on pourrait même dire que tout problème vraiment intéressant est NP-complet. Donc, si vous connaissez un moyen de résoudre any problème NP-complet $ X $ rapidement, vous pouvez prendre tout autre problème NP-complet, la transformer en une instance de $ X $, et résoudre ce rapidement ainsi.

Plusieurs recherches intelligentes ont passé beaucoup de temps sur la recherche de ces problèmes difficiles. Malgré tout ce que nous encore les efforts et les années, ne sont pas un algorithme polynomial pour l'un des problèmes NP-complets. Nous avons également des résultats conditionnels de la forme « si vous pouvez le faire plus vite / mieux, alors P = NP ».

Quant à prouver la demande, nous ne savons peut-être pas bien sûr. Ce que nous savons est que quel que soit l'apparence de preuve aiment, il ne peut pas être d'un certain type. Donc, au moins, si jamais il y avait une preuve, il devra déterminer comment il évite certaines difficultés connues.

Pour plus de détails, vous pouvez d'abord un coup d'oeil au livre de Sipser, puis le livre Arora-Barak.

Answer 2

P ? NP semble être une sorte de « limite de vitesse de calcul » ou « théorème de déjeuner sans libre » ou « goulot d'étranglement fondamental » dont il y a beaucoup d'autres exemples similaires de nombreuses branches de la science, les mathématiques et la physique même. la quantité de calcul nécessaire pour résoudre un problème SAT est exponentielle dans tous les algorithmes connus, et il y a beaucoup qui ont été inventées au fil des ans par les meilleurs chercheurs. des décennies de recherche ont été consacrés à la résolution de SAT seul, en fait plus de ½ siècle de la recherche, par exemple depuis le RJ Lipton .

L'une des raisons de ces postes est que je crois qu'une grande partie de ce que nous croyons en tant que communauté au sujet de P $ de la stackrel {?} {=} $ NP peut être au mieux devinettes et, au pire, tout simplement mal. La plupart pensent que « évidemment » P ? NP, mais je ne suis pas si sûr. Je pense vraiment que le contraire pourrait tout aussi bien tenir.

voir ces beaux sondages par Gasarch

[1] Gasarch P vs NP sondage I, 2002

[2] Gasarch P vs NP sondage II, 2012

comme pour son propre prouvable, il y a un débat d'experts sérieux sur ce sujet. voir cette ref / enquête, et aussi un célèbre papier primé.

[3] est P ? NP formellement indépendant Aaronson

[4] preuves naturelles de Razborov / Rudich

Answer 3

I think that people always believe the conjecture that has "more quantifiers." We always conjecture that "there is no such number as" rather than "there is a number" or that "there are infinitely many such numbers" rather than "there are no more numbers larger than this." One reason should be that we feel that if there was such a number/bound, then we could find it/guess it.

With P=NP, if you thought that they were equal, then you should think that there is an algorithm for SAT, again a constructive thing, which if we cannot show that exits, we conjecture that it does not. At least after a lot of smart people have worked on it and could not find it.

Note that P=NP is different from number theory conjectures, which are based on some empirical evidence, like assuming that primes behave like random numbers. Here there is no supporting assumption, except that until now no one could find an algorithm. I suppose this makes the conjecture "less likely" but of course there can be no formal way of assigning probabilities to mathematical statements.

But probably you are better off reading the opinions of experts, see here: http://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP