Intractabilité des problèmes NP-complets comme principe de la physique?

15

Je suis toujours intrigué par le manque de preuves numériques des mathématiques expérimentales pour ou contre la question P vs NP. Bien que l'hypothèse de Riemann ait des preuves à l'appui de la vérification numérique, je ne connais pas de preuves similaires pour la question P vs NP.

De plus, je ne suis au courant d'aucune conséquence directe sur le monde physique de l'existence de problèmes indécidables (ou de l'existence de fonctions non calculables). Le repliement des protéines est un problème NP-complet mais il semble avoir lieu de manière très efficace dans les systèmes biologiques. Scott Aaronson a proposé d'utiliser l'hypothèse de dureté NP comme principe de physique. Il énonce l'hypothèse de manière informelle car " les problèmes NP-complets sont insolubles dans le monde physique ".

En supposant l'hypothèse de dureté NP, pourquoi est-il difficile de concevoir une expérience scientifique qui décide si notre univers respecte l'hypothèse de dureté NP ou non?

De plus, existe-t-il des preuves numériques connues des mathématiques expérimentales pour ou contre ?PNP

EDIT: Voici une belle présentation de Scott Aaronson intitulée Computational Intractability As A Law of Physics

Mohammad Al-Turkistany
la source
Voici une observation connexe, selon la théorie quantique, chaque quantité physique est discrète, y compris le temps, la longueur, la masse et l'énergie (extrêmement petite). Alors, est-il correct de considérer l'évolution d'un système quantique comme un problème d'optimisation discret régi par le principe de la moindre action sur toutes les trajectoires possibles de l'espace d'état?
Mohammad Al-Turkistany,
8
Le fait que les protéines se replient bien in vivo ne doit pas être considéré comme une preuve que l'univers résout des problèmes NP-complets. Les protéines ont évolué pour se plier efficacement. Il existe même des protéines qui se plient bien dans l'environnement cellulaire et qui ne se plient pas correctement in vitro . En effet, dans la cellule, il existe d'autres protéines appelées chaperonines qui aident au processus de repliement (ces chaperonines ont probablement co-évolué avec les protéines qu'elles aident à replier).
Peter Shor

Réponses:

17

Je ne pense pas que le fait que soit une déclaration asymptotique soit un "dealbreaker" automatique. On peut faire des conjectures concrètes qui sont cohérentes avec nos connaissances mais plus fortes que P vs NP telles que "Il faut au moins 2 n / 10 étapes pour trouver une affectation satisfaisante pour une formule aléatoire 10 n variable 10SAT" (avec "aléatoire" étant par exemple, le modèle planté d' Achlioptas Coja-Oghlan , ce n'est qu'un exemple - je ne sais pas ce que sont des chiffres concrets raisonnables).PNP2n/10

Une telle conjecture peut entraîner une prédiction réfutable que tout système naturel qui tentera de résoudre ce problème échouera (par exemple, restera coincé dans un minimum local), quelque chose que vous pouvez vérifier avec des expériences. En effet, je ne suis pas un expert en la matière, mais à ma connaissance, comme l'a mentionné Joe Fitzsimons, de telles prédictions avaient été confirmées avec l'informatique adiabatique. (Scott Aaronson a également fait des expériences amusantes avec des bulles de savon.)

Bien sûr, vous pouvez également voir des "preuves empiriques" pour dans le fait que les gens ont essayé de résoudre des problèmes d'optimisation, de crypto-analyse des cryptages, etc. et n'ont pas réussi jusqu'à présent ...PNP

Boaz Barak
la source
2
@Jeff - Je pense que cela prouve que P n'est pas égal à NP de la même manière que le fait que tous les nombres que nous avons essayés jusqu'à présent ont suivi la conjecture de Goldbach est une preuve évidente en faveur de la conjecture de Goldbach et pas seulement en notre faveur de choisir le mauvais numéros.
Vinayak Pathak
3
Boaz: Je serais peut-être prêt à l'accepter comme preuve de l'hypothèse la plus faible "CET algorithme a besoin d'au moins étapes", mais pas de l'hypothèse plus forte "TOUT algorithme a besoin d'au moins 2 n / 10 étapes". Il y a tout simplement trop (en fait, infiniment) d'algorithmes non testés, ou même de classes d'algorithmes, pour que j'accepte que n'importe quel expérimentateur ait essayé un échantillon représentatif. 2n/dix2n/dix
Jeffε
6
Si vous pouviez montrer en quelque sorte que l'algorithme de recherche universel de Levin a besoin de étapes, alors vous montrez que n'importe quel algorithme a effectivement besoin de ce nombre ... bien sûr, compte tenu de nos connaissances actuelles, ce serait incroyablement difficile à mettre en œuvre et à tester. 2n/dix
Ryan Williams
3
Ryan - en pratique, vous ne pourrez énumérer que des programmes avec une très petite taille de description. (Voir aussi l'article de Luca Trevisan - eccc.hpi-web.de/report/2010/034/download )
Boaz Barak
2
JeffE - supposons que certaines preuves provenant d'un autre domaine scientifique suggèrent qu'un système naturel peut atteindre rapidement son minimum global, tandis que l' hypothèse (renforcée) prédit qu'il se coince au minimum local, et il s'avère que ce dernier est vrai. Cela me semble être au moins une preuve P N P . Ce ne sont pas des preuves concluantes, mais au fur et à mesure que ces choses s'accumulent, s'il s'avère (renforcé) que P N P a un pouvoir prédictif positif, c'est un argument pour en faire une "loi de la nature". (Cela vaut pour au moins tous les algorithmes / systèmes naturels que nous avons rencontrés jusqu'à présent ...)PNPPNPPNP
Boaz Barak
15

Le monde réel est un objet de taille constante, il n'y a donc aucun moyen d'exclure une procédure en temps réel polynomial pour résoudre des problèmes NP-complets qui ont une énorme constante cachée dans la grande notation O.

Quoi qu'il en soit, outre ce point, l'hypothèse est une déclaration de la forme "il n'y a pas de procédure réelle qui le fasse ..." Comment concevoir une expérience pour réfuter une telle déclaration? Si l'hypothèse était quelque chose comme "Si nous faisons X dans le monde réel, Y arrive", alors cela peut être réfuté en exécutant X. La déclaration que nous voulons affirme la non-existence de quelque chose, donc je ne peux pas voir une expérience le décider. Cela pourrait être montré comme une conséquence physique des lois de la physique, mais c'est encore plus difficile que P vs NP, car une machine de Turing suit les lois de la physique. Puisque nous avons échoué même à montrer que les MT ne peuvent pas résoudre les problèmes NP-complets en temps polynomial, il semble complètement désespéré de montrer qu'aucun processus physique ne peut résoudre les problèmes NP-complets en temps polynomial.

Robin Kothari
la source
1
Si le monde réel est un objet de taille constante, alors tous les ordinateurs construits à ce jour sont des automates finis.
Peter Shor
12

En effet la version physique de P non égale à NP, à savoir qu'aucun système physique naturel ne peut résoudre le problème complet de NP est très intéressante. Il y a quelques préoccupations

1) Le programme semble pratiquement "orthogonal" à la fois à la physique expérimentale et théorique. Il ne fournit donc pas (jusqu'à présent) d'idées utiles en physique.

Il y a de beaux arguments sur la façon dont on peut déduire de cette version physique de la conjecture quelques aperçus en physique, mais ces arguments sont assez "mous" et ont des failles. (Et de tels arguments sont susceptibles d'être problématiques, car ils reposent sur des conjectures mathématiques très difficiles telles que NP non différent de P, et NP non inclus dans BQP que nous ne comprenons pas.)

(Un commentaire similaire s'applique à la "thèse de Church-turing".)

2) Bien que le NP physique non égal à P soit une conjecture plus large que le NP mathématique non égal à P, nous pouvons également le considérer comme plus restreint car les algorithmes qui se produisent dans la nature (et même les algorithmes créés par les hommes) semblent être très classe restreinte de tous les algorithmes théoriquement possibles. Il sera très intéressant de comprendre formellement de telles restrictions, mais dans tous les cas, toute "preuve" exerimental suggérée dans la question ne s'appliquera qu'à ces classes restreintes.

3) Dans la modélisation scientifique, la complexité informatique représente une sorte de matière de second ordre où nous aimerions d'abord modéliser un phénomène naturel et voir ce qui peut être prédit sur la base du modèle (en mettant de côté la théorie de la complexité informatique). Accorder trop de poids aux problèmes de complexité de calcul à l'étape de la modélisation ne semble pas être fructueux. Dans de nombreux cas, le modèle est difficilement calculable pour commencer, mais il peut toujours être possible pour des problèmes naturels ou utile pour comprendre les phénomènes.

4) Je suis d'accord avec Boaz sur le fait que la question asymptotique n'est pas nécessairement un "briseur d'accord". Pourtant, c'est une question assez sérieuse en ce qui concerne la pertinence des questions de complexité de calcul pour la modélisation de la vie réelle.

Gil Kalai
la source
11

Si vous me permettez de généraliser un tout petit peu ... Étendons la question et demandons d'autres hypothèses de dureté théoriquement complexes et leurs conséquences pour les expériences scientifiques. (Je vais me concentrer sur la physique.) Récemment, il y a eu un programme plutôt réussi pour essayer de comprendre l'ensemble des corrélations autorisées entre deux appareils de mesure qui, bien que spatialement séparés, effectuent une mesure sur un système physique (éventuellement non corrélé localement) ( 1). Sous cette configuration et des configurations similaires, on peut utiliser les hypothèses sur la dureté de la complexité de la communication pour dériver des limites strictes qui reproduisent les corrélations autorisées pour la mécanique quantique.

Pour vous donner une saveur, permettez-moi de décrire un résultat antérieur à cet égard. UNE boîte Popescu-Rohrlich (ou boîte PR) est un appareil imaginaire qui reproduit des corrélations entre les appareils de mesure qui sont conformes au principe selon lequel aucune information ne peut voyager plus vite que la lumière (appelée principe de non-signalisation ).

S. Popescu & D. Rohrlich, La non-localité quantique comme axiome, Trouvé. Phys. 24, 379–385 (1994).

Nous pouvons voir cela comme un exemple de complexité de communication ayant une certaine influence. L'idée que deux observateurs doivent communiquer suppose implicitement une certaine contrainte qu'un physicien n'appellerait pas de signalisation. Pour inverser cette idée, quels types de corrélations sont possibles entre deux appareils de mesure contraints par l'absence de signalisation? C'est ce que Popescu & Rohrlich étudient. Ils ont montré que cet ensemble de corrélations admissibles est strictement supérieur à ceux autorisés par la mécanique quantique, qui sont à leur tour strictement supérieurs à ceux autorisés par la physique classique.

La question se pose alors, qu'est-ce qui fait de l'ensemble des corrélations quantiques le "bon" ensemble de corrélations, et non celles permises par l'absence de signalisation?

Pour répondre à cette question, supposons à nu qu'il existe des fonctions pour lesquelles la complexité de la communication n'est pas triviale. Ici, non trivial signifie simplement que pour calculer conjointement une fonction booléenne f (x, y), cela prend plus qu'un simple bit (2). Et bien étonnamment, même cette très faible hypothèse théorique de complexité est suffisante pour restreindre l'espace des corrélations permises.

G. Brassard, H. Buhrman, N. Linden, AA Méthot, A. Tapp et F. Unger, Limit on Nonlocality in Any World in which Communication Complexity Is Not Trivial, Phys. Rev. Lett. 96, 250401 (2006).

Notez qu'un résultat plus faible a déjà été prouvé dans le doctorat. thèse de Wim van Dam. Ce que Brassard et al. est que l'accès aux boîtiers PR, même ceux qui sont défectueux et ne produisent que la corrélation correcte une partie du temps, permet de banaliser complètement la complexité de la communication. Dans ce monde, chaque fonction booléenne à deux variables peut être calculée conjointement en ne transmettant qu'un seul bit. Cela semble assez absurde, alors regardons-le à l'inverse. Nous pouvons prendre la non-trivialité de la complexité de la communication comme un axiome, ce qui nous permet de dériver le fait que nous n'observons pas certaines corrélations plus fortes que quantiques dans nos expériences.

Ce programme utilisant la complexité de la communication a connu un succès surprenant, peut-être bien plus que celui correspondant à la complexité informatique. Les articles ci-dessus ne sont vraiment que la pointe de l'iceberg. Un bon endroit pour commencer la lecture est cette revue:

H. Buhrman, R. Cleve, S. Massar et R. de Wolf, Non-localité et complexité de la communication, Rév. Mod. Phys. 82, 665–698 (2010).

ou une recherche documentaire à partir des deux autres articles que j'ai cités.

Cela soulève également la question intéressante de savoir pourquoi le paramètre de communication semble beaucoup plus adapté à l'analyse que le paramètre de calcul. Cela pourrait peut-être faire l'objet d'une autre question publiée sur la théorie.


(1) Prenons par exemple les expériences mesurant quelque chose connu sous le nom d'inégalité CHSH (un type d' inégalité de Bell ), où le système physique se compose de deux photons intriqués, et les mesures sont des mesures de polarisation sur les photons individuels à deux endroits spatialement éloignés.

(2) Ce bit unique est nécessaire chaque fois que f (x, y) dépend à la fois de x et y, car l'envoi de zéro bit ne violerait aucune signalisation.

Steve Flammia
la source
7

De plus, existe-t-il des preuves numériques connues des mathématiques expérimentales pour ou contre P ≠ N PPNP

NPP/poly

Maintenant, trouver un circuit minimum pour SAT jusqu'à la longueur 10 est actuellement très difficile. Cependant, certaines des idées de la théorie de la complexité géométrique vous permettent d'obtenir des résultats similaires avec une recherche informatique plus efficace (je pense seulement exponentielle au lieu de doublement exponentielle). L'une des conjectures de Mulmuley est qu'en fait cette recherche peut se faire en temps polynomial, mais nous sommes loin de prouver quoi que ce soit de proche.

Joshua Grochow
la source
Pourriez-vous nous expliquer comment utiliser GCT pour améliorer la recherche par force brute?
arnab
gLngLn
NPP/poly
@Ryan: Excellent point de clarification. Cela m'a amené à m'interroger sur cette question: cstheory.stackexchange.com/questions/1514/…
Joshua Grochow
6

Les définitions du «temps polynomial» et du «temps exponentiel» décrivent le comportement limitant du temps de fonctionnement lorsque la taille d'entrée augmente à l'infini. D'un autre côté, toute expérience physique ne considère nécessairement que des entrées de taille limitée. Ainsi, il n'y a absolument aucun moyen de déterminer expérimentalement si un algorithme donné s'exécute en temps polynomial, en temps exponentiel ou autre.

Ou en d'autres termes: ce que Robin a dit.

Jeffε
la source
Supposons que plusieurs expériences soient effectuées qui codent d'une manière ou d'une autre des problèmes NP-complets en problèmes réels et laissent la nature les résoudre. Et supposons que dans toutes ces expériences, on découvre qu'il existe une taille d'entrée suffisamment grande pour laquelle la nature prend beaucoup de temps à résoudre le problème, alors cela sera-t-il une preuve en faveur de l'affirmation selon laquelle la nature ne peut pas résoudre les problèmes NP-complets efficacement?
Vinayak Pathak
1
Absolument pas. Même si vous pouviez convaincre la Nature de résoudre les problèmes de manière optimale (contrairement aux bulles de savon pour les arbres Steiner, par exemple), et même si vous pouviez distinguer un comportement asymptotique d'une expérience finie, il se pourrait que la Nature utilise un algorithme inefficace.
Jeffε
1
(D'un point de vue philosophique, je ne vois tout simplement pas de différence entre "convaincre la nature de résoudre le problème" et "implémenter et exécuter un algorithme pour résoudre le problème". D'une part, "une technique fiable pour faire un système physique résoudre un problème "est une définition pratique de l'algorithme; d'autre part, les humains et les ordinateurs font tous deux partie de la nature.)
Jeffε
5

Permettez-moi de commencer en disant que je suis entièrement d'accord avec Robin. En ce qui concerne le repliement des protéines, il y a un petit problème. Comme avec tous ces systèmes, le repliement des protéines peut rester bloqué dans les minima locaux, ce que vous semblez négliger. Le problème plus général consiste simplement à trouver l'état fondamental d'un hamiltonien. En fait, même si nous considérons uniquement les spins (c'est-à-dire les qubits), ce problème est complet pour QMA.

Les hamiltoniens naturels sont un peu plus mous, cependant, que certains des artificiels utilisés pour prouver l'exhaustivité de l'AMQ (qui ont tendance à ne pas refléter les interactions naturelles), mais même lorsque nous nous limitons aux interactions naturelles à deux corps sur des systèmes simples, le résultat est toujours un NP -problème complet. En effet, cela constitue la base d'une approche tentée pour résoudre les problèmes de NP en utilisant l'informatique quantique adiabatique. Malheureusement, il semble que cette approche ne fonctionnera pas pour les problèmes NP-complets, en raison d'un problème plutôt technique lié à la structure du niveau d'énergie. Cela conduit cependant à une conséquence intéressante de l'existence de problèmes au sein de NP qui ne sont pas efficacement résolubles par nature (j'entends par là des processus physiques). Cela signifie qu'il existe des systèmes qui ne peuvent pas refroidir efficacement. C'est-à-dire,

Joe Fitzsimons
la source
Corrigez-moi si je me trompe, pensez-vous que l'hypothèse de dureté NP doit avoir des conséquences physiquement observables?
Mohammad Al-Turkistany
Je dis que si BQP ne contient pas de NP (ce qui semble certainement être le cas), le NP étant dur a certainement des conséquences physiques. Pour les systèmes très bruyants, il semblerait que nous pourrions nous débarrasser de l'étape BQP et obtenir le résultat directement de NP étant difficile, mais cela nécessite quelques hypothèses physiques.
Joe Fitzsimons
PNPP=NP
4

L'étude des situations du monde réel d'un point de vue informatique est assez difficile en raison du «saut» discret continu. Alors que tous les événements du monde réel (soi-disant) sont exécutés en temps continu, les modèles que nous utilisons habituellement sont mis en œuvre en temps discret. Par conséquent, il est très difficile de définir la taille d'une étape, quelle doit être la taille du problème, etc.

J'ai écrit un résumé sur un article d'Aaronson sur le sujet, mais il n'est pas en anglais. Voir le papier d'origine .

Personnellement, j'ai entendu parler d'un autre exemple d'un problème du monde réel modélisé dans le calcul. L'article porte sur des modèles de systèmes de contrôle basés sur le vol d'oiseaux. Il s'avère que même si cela prend peu de temps dans la vie réelle pour les oiseaux, il est intraitable ("une tour de 2") lorsqu'il est analysé comme un problème de calcul. Voir l'article de Bernard Chazelle pour plus de détails.

[Edit: Clarifié la partie sur le papier Chazelle. Merci d'avoir fourni des informations précises.]

chazisop
la source
2
pas seulement exponentielle. c'est une tour de 2 en fait.
Suresh Venkat
1
Suresh est, bien sûr, correct. Au-delà de cela, l'article de Chazelle n'est pas une analyse du vol d'oiseaux: c'est une analyse de modèles de systèmes de contrôle bien connus basés sur le vol d'oiseaux. En particulier, son analyse nécessite l'utilisation d'une «règle d'hystérésis» selon laquelle les oiseaux ne sont pas observés à obéir eux-mêmes. Voir le commentaire # 3 de Chazelle ici pour en savoir plus sur ce programme de recherche.
Aaron Sterling,
0

Je vote toujours pour le problème des n-corps en tant qu'exemple de l'intraitabilité du NP. Les messieurs qui se réfèrent aux solutions numériques oublient que la solution numérique est un modèle récursif, et non une solution en principe de la même manière qu'une solution analytique. La solution analytique de Qui Dong Wang est intraitable. Les protéines qui peuvent se replier et les planètes qui peuvent orbiter dans des systèmes de plus de deux corps sont des systèmes physiques, et non des solutions algorithmiques du type de celles que le problème P-NP aborde.

Je dois également apprécier les difficultés de Chazisop avec les solutions en temps continu. Si le temps ou l'espace est continu, les espaces d'état potentiels deviennent innombrables (aleph one).

James McIntosh
la source
2
Le problème exact / analogique à 3 corps n'est pas seulement difficile à NP; c'est indécidable . D'un autre côté, les vrais systèmes physiques ne sont pas vraiment analogiques; vous venez de remplacer une abstraction mathématique par une autre.
Jeffε
-1

Nous ne pouvons pas résoudre efficacement le nproblème de corps, mais ces planètes de roches pour le cerveau semblent se débrouiller très bien.


la source
2
Ce n'est pas vrai. On peut en effet résoudre efficacement le problème des n-corps, c'est simplement qu'il n'y a pas de solution analytique. Les méthodes numériques fonctionnent très bien.
Joe Fitzsimons
6
Exactement. Je n'ai jamais vu une planète présenter une solution analytique pour le problème des n-corps non plus, donc la comparaison est injuste.
Robin Kothari