Intraktabilität von NP-vollständigen Problemen als physikalisches Prinzip?

15

Ich bin immer fasziniert von dem Mangel an numerischen Beweisen aus der experimentellen Mathematik für oder gegen die P vs NP-Frage. Während die Riemann-Hypothese einige Belege aus der numerischen Verifikation enthält, sind mir keine ähnlichen Belege für die P-gegen-NP-Frage bekannt.

Außerdem sind mir keine direkten Konsequenzen für die physische Welt bekannt, die sich aus der Existenz unentscheidbarer Probleme (oder der Existenz nicht berechenbarer Funktionen) ergeben. Die Proteinfaltung ist ein NP-vollständiges Problem, scheint jedoch in biologischen Systemen sehr effizient zu sein. Scott Aaronson schlug vor, die NP-Härteannahme als physikalisches Prinzip zu verwenden. Er gibt die Annahme informell als " NP-vollständige Probleme sind in der physischen Welt unlösbar " an.

Unter der Annahme der NP-Härteannahme, warum ist es schwierig, ein wissenschaftliches Experiment zu entwerfen, das entscheidet, ob unser Universum die NP-Härteannahme respektiert oder nicht?

Gibt es auch bekannte numerische Beweise aus der experimentellen Mathematik für oder gegen ?PNP

EDIT: Hier ist eine schöne Präsentation von Scott Aaronson mit dem Titel Computational Intractability As A Law of Physics

Mohammad Al-Turkistany
quelle
Hier ist eine verwandte Beobachtung, nach der Quantentheorie ist jede physikalische Größe diskret, einschließlich Zeit, Länge, Masse und Energie (extrem klein). Ist es also richtig, die Evolution eines Quantensystems als ein diskretes Optimierungsproblem anzusehen, das durch das Prinzip der geringsten Wirkung über alle möglichen Zustandsraumtrajektorien bestimmt wird?
Mohammad Al-Turkistany
8
Die Tatsache, dass sich Proteine in vivo gut falten, sollte nicht als Beweis dafür gewertet werden, dass das Universum NP-vollständige Probleme löst. Proteine ​​haben sich entwickelt, um sich effizient zu falten. Es gibt sogar einige Proteine, die sich in der zellulären Umgebung gut falten und sich in vitro nicht richtig falten . Dies liegt daran, dass es in der Zelle andere Proteine ​​gibt, die Chaperonine genannt werden und den Faltungsprozess unterstützen (diese Chaperonine haben sich vermutlich zusammen mit den Proteinen entwickelt, die sie bei der Faltung unterstützen).
Peter Shor

Antworten:

17

Ich denke nicht, dass die Tatsache, dass eine asymptotische Aussage ist, ein automatischer "Dealbreaker" ist. Man kann konkrete Vermutungen anstellen, die mit unserem Wissen übereinstimmen, aber stärker als P gegen NP sind, wie zum Beispiel "Es braucht mindestens"PNP Schritte erforderlich, um eine zufriedenstellende Zuordnung für eine zufällige n-Variable 10SAT-Formel zu finden" (wobei "zufällig" beispielsweise ist). Das bepflanzte Modell vonAchlioptas Coja-Oghlanist nur ein Beispiel (ich weiß nicht, was vernünftige konkrete Zahlen sind).2n/10

Eine solche Vermutung kann zu einer widerlegbaren Vorhersage führen, dass jedes natürliche System, das versucht, dies zu lösen, versagt (z. B. in einer lokalen Minima stecken bleibt), was Sie anhand von Experimenten überprüfen können. In der Tat bin ich kein Experte auf diesem Gebiet, aber meines Wissens, wie Joe Fitzsimons erwähnte, waren solche Vorhersagen mit Adiabatic Computing bestätigt worden. (Scott Aaronson hatte auch einige unterhaltsame Experimente mit Seifenblasen.)

Natürlich können Sie auch einige „empirische Evidenz“ für siehe in der Tatsache sehen, dass die Leute versucht haben, Optimierungsprobleme zu lösen, Verschlüsselungen zu verschlüsseln usw. und bisher nicht erfolgreich waren ...PNP

Boaz Barak
quelle
2
@ Jeff - Ich denke, dies ist ein Beweis dafür, dass P nicht gleich NP ist wie die Tatsache, dass alle Zahlen, die wir bisher ausprobiert haben, Goldbachs Vermutung gefolgt sind, spricht für Goldbachs Vermutung und nicht nur dafür, dass wir uns für die entscheiden falsche Zahlen.
Vinayak Pathak
3
Boaz: Ich bin vielleicht bereit, dies als Beweis für die schwächere Hypothese "DIESER Algorithmus benötigt mindestens Schritte" zu akzeptieren , aber nicht für die stärkere Hypothese "JEDER Algorithmus benötigt mindestens 2 n / 10 Schritte". Es gibt einfach zu viele (tatsächlich unendlich viele) unversuchte Algorithmen oder sogar Klassen von Algorithmen, als dass ich akzeptieren könnte, dass ein Experimentator eine repräsentative Stichprobe ausprobiert hat. 2n/102n/10
Jeffs
6
Wenn Sie irgendwie zeigen könnten, dass der universelle Suchalgorithmus von Levin Schritte benötigt, dann zeigen Sie effektiv, dass jeder Algorithmus so viele benötigt ... natürlich wäre dies nach unserem derzeitigen Kenntnisstand wahnsinnig unpraktisch zu implementieren und zu testen. 2n/10
Ryan Williams
3
Ryan - in der Praxis können Sie nur Programme mit sehr kleiner Beschreibungsgröße aufzählen. (Siehe auch Luca Trevisans Artikel - eccc.hpi-web.de/report/2010/034/download )
Boaz Barak,
2
JeffE - Angenommen, einige Beweise aus einem anderen wissenschaftlichen Bereich legen nahe, dass ein natürliches System schnell sein globales Minimum erreicht, während die (verstärkte) Annahme voraussagt, dass es an einem lokalen Minimum hängen bleibt, und es sich herausstellt, dass letzteres zutrifft. Das scheint mir zumindest ein Beweis für P N P zu sein . Es ist kein schlüssiger Beweis, aber da sich diese Dinge ansammeln, stellt sich heraus (verstärkt) P N PPNPPNPPNP eine positive Vorhersagekraft hat, ist dies ein Argument dafür, dass es ein "Naturgesetz" ist. (Das gilt zumindest für alle Algorithmen / natürlichen Systeme, denen wir bisher begegnet sind ...)
Boaz Barak
15

Die reale Welt ist ein Objekt mit konstanter Größe. Es gibt also keine Möglichkeit, eine Prozedur in der realen Welt in Polynomzeit auszuschließen, um NP-vollständige Probleme zu lösen, bei denen eine große Konstante in der großen O-Notation verborgen ist.

Abgesehen von diesem Punkt ist die Annahme jedenfalls eine Aussage der Form "Es gibt kein Verfahren in der realen Welt, das ...". Wie kann man ein Experiment entwerfen, um eine solche Aussage zu widerlegen? Wenn die Annahme so war wie "Wenn wir X in der realen Welt machen, passiert Y", dann kann dies durch Ausführen von X widerlegt werden. Die Aussage, die wir wollen, behauptet die Nichtexistenz von etwas, also kann ich kein Experiment sehen es entscheiden. Es könnte als physikalische Konsequenz der Gesetze der Physik gezeigt werden, aber dies ist noch schwieriger als P gegen NP, weil eine Turing-Maschine den Gesetzen der Physik folgt. Da es uns nicht gelungen ist zu zeigen, dass TMs NP-vollständige Probleme in der Polynomzeit nicht lösen können, scheint es völlig hoffnungslos zu zeigen, dass kein physikalischer Prozess NP-vollständige Probleme in der Polynomzeit lösen kann.

Robin Kothari
quelle
1
Wenn die reale Welt ein Objekt mit konstanter Größe ist, sind alle bisher gebauten Computer endliche Automaten.
Peter Shor
12

In der Tat ist die physikalische Version von P ungleich NP, nämlich dass keine natürlichen physikalischen Systeme das NP-Gesamtproblem lösen können, sehr interessant. Es gibt einige Bedenken

1) Das Programm scheint sowohl für die experimentelle als auch für die theoretische Physik praktisch "orthogonal" zu sein. Es liefert also (bisher) keine wirklich nützlichen Erkenntnisse in der Physik.

Es gibt einige nette Argumente, wie man aus dieser physikalischen Version der Vermutung einige physikalische Einsichten ableiten kann, aber diese Argumente sind ziemlich "weich" und haben Lücken. (Und solche Argumente sind wahrscheinlich problematisch, da sie sich auf sehr schwierige mathematische Vermutungen stützen, z. B. NP ungleich P und NP nicht in BQP enthalten sind, die wir nicht verstehen.)

(Ein ähnlicher Kommentar gilt für die "kirchliche These".)

2) Obwohl der physikalische NP ungleich P eine breitere Vermutung ist als der mathematische NP ungleich P, können wir ihn auch als eingeschränkter betrachten, da die in der Natur vorkommenden Algorithmen (und sogar die von Menschen gemachten Algorithmen) sehr ähnlich zu sein scheinen eingeschränkte Klasse aller theoretisch möglichen Algorithmen. Es wird sehr interessant sein, solche Einschränkungen formal zu verstehen, aber in jedem Fall gilt jeder experimentelle "Beweis", wie in der Frage vorgeschlagen, nur für diese eingeschränkte Klasse.

3) In der wissenschaftlichen Modellierung stellt die rechnerische Komplexität eine Art Angelegenheit zweiter Ordnung dar, bei der wir zunächst ein natürliches Phänomen modellieren und sehen möchten, was auf der Grundlage des Modells vorhergesagt werden kann (ohne rechnerische Komplexitätstheorie). Es scheint nicht fruchtbar zu sein, Fragen der Rechenkomplexität in der Modellierungsphase zu viel Gewicht zu geben. In vielen Fällen ist das Modell anfangs rechenintensiv, es kann jedoch für natürlich auftretende Probleme noch praktikabel oder zum Verständnis der Phänomene nützlich sein.

4) Ich stimme Boaz zu, dass das asymptotische Problem kein "Deal Breaker" ist. Dennoch ist es eine ziemlich ernste Angelegenheit, wenn es um die Relevanz von Rechenkomplexitätsaspekten für die Modellierung des realen Lebens geht.

Gil Kalai
quelle
11

Wenn Sie mir erlauben, ein kleines bisschen zu verallgemeinern ... Lassen Sie uns die Frage erweitern und nach anderen komplexitätstheoretischen Härteannahmen und deren Konsequenzen für wissenschaftliche Experimente fragen. (Ich werde mich auf die Physik konzentrieren.) Vor kurzem gab es ein ziemlich erfolgreiches Programm, um zu versuchen, die Menge der zulässigen Korrelationen zwischen zwei Messgeräten zu verstehen, die, obwohl räumlich getrennt, eine Messung an einem (möglicherweise nicht lokal korrelierten) physikalischen System durchführen ( 1). Unter diesen und ähnlichen Bedingungen kann man die Annahmen über die Härte der Kommunikationskomplexität verwenden , um enge Grenzen abzuleiten, die die zulässigen Korrelationen für die Quantenmechanik reproduzieren.

Um Ihnen einen Vorgeschmack zu geben, lassen Sie mich diesbezüglich ein früheres Ergebnis beschreiben. Eine Popescu-Rohrlich-Box (oder PR-Box) ist ein imaginäres Gerät, das Korrelationen zwischen den Messgeräten reproduziert, die mit dem Prinzip übereinstimmen, dass sich keine Information schneller als Licht ausbreiten kann (so genanntes Prinzip ohne Signalisierung ).

S. Popescu & D. Rohrlich, Quantum Nonlocality als Axiom, Found. Phys. 24, 379–385 (1994).

Wir können dies als einen Fall von Kommunikationskomplexität betrachten, der einen gewissen Einfluss hat. Die Vorstellung, dass zwei Beobachter implizit kommunizieren müssen , setzt eine Einschränkung voraus, die ein Physiker als nicht signalisierend bezeichnen würde. Um diese Idee umzukehren, welche Arten von Korrelationen sind zwischen zwei Messgeräten möglich, die durch keine Signalisierung eingeschränkt werden? Das studiert Popescu & Rohrlich. Sie zeigten, dass diese Menge zulässiger Korrelationen streng größer ist als die der Quantenmechanik, die wiederum streng größer ist als die der klassischen Physik.

Dann stellt sich die Frage, was die Menge der Quantenkorrelationen zur "richtigen" Menge von Korrelationen macht und nicht die, die durch keine Signalisierung zugelassen werden.

Nehmen wir zur Beantwortung dieser Frage an, dass es Funktionen gibt, für die die Kommunikationskomplexität nicht trivial ist. Nicht-trivial bedeutet hier nur, dass für die gemeinsame Berechnung einer Booleschen Funktion f (x, y) mehr als nur ein einziges Bit benötigt wird (2). Überraschenderweise reicht auch diese sehr schwache komplexitätstheoretische Annahme aus, um den Raum für zulässige Korrelationen einzuschränken.

G. Brassard, H. Buhrman, N. Linden, A. Méthot, A. Tapp und F. Unger, Beschränkung der Nichtlokalität in jeder Welt, in der die Kommunikationskomplexität nicht trivial ist, Phys. Rev. Lett. 96, 250401 (2006).

Beachten Sie, dass ein schwächeres Ergebnis bereits in der Promotion nachgewiesen wurde. These von Wim van Dam. Was Brassard et al. beweisen, dass man durch den Zugriff auf PR-Boxen, auch wenn diese fehlerhaft sind und nur zeitweise die richtige Korrelation herstellen, die Komplexität der Kommunikation vollständig trivialisieren kann. In dieser Welt kann jede Boolesche Funktion mit zwei Variablen gemeinsam berechnet werden, indem nur ein einziges Bit übertragen wird. Das scheint ziemlich absurd zu sein, also schauen wir es uns umgekehrt an. Wir können die Nicht-Trivialität der Kommunikationskomplexität als Axiom betrachten und daraus ableiten , dass wir in unseren Experimenten keine bestimmten Korrelationen beobachten, die stärker als die Quanten sind.

Dieses Programm, das Kommunikationskomplexität verwendet, war überraschend erfolgreich, vielleicht sogar weitaus erfolgreicher als das entsprechende Programm für Rechenkomplexität. Die obigen Papiere sind wirklich nur die Spitze des Eisbergs. Ein guter Ort, um weiterzulesen, ist diese Rezension:

H. Buhrman, R. Cleve, S. Massar und R. de Wolf, Nichtlokalität und Kommunikationskomplexität, Rev. Mod. Phys. 82, 665–698 (2010).

oder eine vorausschauende Literaturrecherche aus den beiden anderen von mir zitierten Arbeiten.

Dies wirft auch die interessante Frage auf, warum die Kommunikationseinstellung für eine Analyse viel besser geeignet erscheint als die Berechnungseinstellung. Vielleicht könnte dies das Thema einer anderen Frage auf cstheory sein.


(1) Nehmen wir zum Beispiel die Experimente zur Messung einer sogenannten CHSH-Ungleichung (eine Art Bell-Ungleichung ), bei der das physikalische System aus zwei verschränkten Photonen besteht und die Messungen Polarisationsmessungen an den einzelnen Photonen an zwei räumlich entfernten Orten sind.

(2) Dieses einzelne Bit ist immer dann erforderlich, wenn f (x, y) tatsächlich von x und y abhängt, da das Senden von Null- Bits keine Signalisierung verletzen würde.

Steve Flammia
quelle
7

Gibt es auch bekannte numerische Beweise aus der experimentellen Mathematik für oder gegen P ≠ N PPNP

NPP/poly

Derzeit ist es sehr schwierig, einen Mindestschaltkreis für SAT bis zur Länge 10 zu finden. Einige der Ideen in der geometrischen Komplexitätstheorie ermöglichen es Ihnen jedoch, ähnliche Ergebnisse mit einer effizienteren (ich denke nur exponentiellen statt doppelt exponentiellen) rechnerischen Suche zu erhalten. Eine der Vermutungen von Mulmuley ist, dass diese Suche tatsächlich in polynomialer Zeit durchgeführt werden kann, aber wir sind weit davon entfernt, irgendetwas in der Nähe davon zu beweisen.

Joshua Grochow
quelle
Könnten Sie näher erläutern, wie Sie mit GCT die Brute-Force-Suche verbessern können?
Arnab
GLnGLn
NPP/poly
@ Ryan: Hervorragender Klärungspunkt. Ich habe mich über diese Frage gewundert
Joshua Grochow
6

Die Definitionen von "Polynomialzeit" und "Exponentialzeit" beschreiben das begrenzende Verhalten der Laufzeit, wenn die Eingabegröße auf unendlich ansteigt. Andererseits berücksichtigt jedes physikalische Experiment notwendigerweise nur Eingaben mit begrenzter Größe. Daher gibt es absolut keine Möglichkeit, experimentell zu bestimmen, ob ein gegebener Algorithmus in Polynomzeit, Exponentialzeit oder etwas anderem abläuft.

Oder mit anderen Worten: was Robin gesagt hat.

Jeffε
quelle
Angenommen, es werden mehrere Experimente durchgeführt, die NP-vollständige Probleme in reale Probleme umwandeln und von der Natur lösen lassen. Angenommen, in all diesen Experimenten wird festgestellt, dass es eine ausreichend große Eingabegröße gibt, für die die Natur viel Zeit zur Lösung des Problems benötigt, dann spricht dies für die Aussage, dass die Natur NP-vollständige Probleme nicht lösen kann effizient?
Vinayak Pathak
1
Absolut nicht. Selbst wenn Sie die Natur davon überzeugen könnten, die Probleme optimal zu lösen (im Gegensatz zu Seifenblasen für Steiner-Bäume), und selbst wenn Sie asymptotisches Verhalten von einem endlichen Experiment unterscheiden könnten, könnte es dennoch vorkommen, dass die Natur einen ineffizienten Algorithmus verwendet.
Jeffs
1
(Aus philosophischer Sicht sehe ich einfach keinen Unterschied zwischen "die Natur überzeugen, das Problem zu lösen" und "einen Algorithmus implementieren und ausführen, um das Problem zu lösen". Einerseits "eine zuverlässige Technik, um ein physikalisches System herzustellen ein Problem lösen "ist eine praktikable Definition des Algorithmus; auf der anderen Seite sind Mensch und Computer Teil der Natur.)
Jeffs
5

Lassen Sie mich zunächst sagen, dass ich Robin vollkommen zustimme. In Bezug auf die Proteinfaltung gibt es ein kleines Problem. Wie bei allen derartigen Systemen kann die Proteinfaltung in lokalen Minima stecken bleiben, was Sie scheinbar vernachlässigen. Das allgemeinere Problem besteht darin, einfach den Grundzustand eines Hamiltonianers zu finden. Selbst wenn wir nur Spins (dh Qubits) berücksichtigen, ist dieses Problem für QMA tatsächlich vollständig.

Natürliche Hamiltonianer sind jedoch etwas weicher als einige der künstlichen, die zum Nachweis der QMA-Vollständigkeit verwendet werden (was die natürlichen Wechselwirkungen nicht widerspiegelt), aber selbst wenn wir uns auf natürliche Zweikörperwechselwirkungen auf einfachen Systemen beschränken, ist das Ergebnis immer noch ein NP -vollständiges Problem. Tatsächlich bildet dies die Grundlage für einen Ansatz, mit dem versucht wird, NP-Probleme mithilfe des adiabatischen Quantencomputers zu lösen. Leider scheint dieser Ansatz aufgrund eines eher technischen Problems im Zusammenhang mit der Struktur des Energieniveaus nicht für NP-vollständige Probleme zu funktionieren. Dies führt jedoch zu einer interessanten Folge der bestehenden Probleme innerhalb von NP, die von Natur aus nicht effizient lösbar sind (womit ich physikalische Prozesse meine). Dies bedeutet, dass es Systeme gibt, die nicht effizient kühlen können. Das heißt,

Joe Fitzsimons
quelle
Korrigieren Sie mich, wenn ich falsch liege. Implizieren Sie, dass die NP-Härte-Annahme physikalisch beobachtbare Konsequenzen haben muss?
Mohammad Al-Turkistany
Ich sage, wenn BQP kein NP enthält (was sicherlich der Fall zu sein scheint), dann hat es sicherlich physikalische Konsequenzen, wenn NP hart ist. Bei sehr lauten Systemen scheint es, als könnten wir die BQP-Stufe loswerden und das Ergebnis direkt erhalten, wenn NP hart ist, aber dies erfordert einige physikalische Annahmen.
Joe Fitzsimons
PNPP=NP
4

Das Studium realer Situationen aus einer rechnerischen Perspektive ist aufgrund des kontinuierlich-diskreten "Sprungs" ziemlich schwierig. Während alle Ereignisse in der realen Welt (angeblich) in kontinuierlicher Zeit ablaufen, werden die von uns üblicherweise verwendeten Modelle in diskreter Zeit implementiert. Daher ist es sehr schwierig zu definieren, wie klein oder groß ein Schritt sein soll, wie groß das Problem sein soll usw.

Ich habe eine Zusammenfassung zu einem Aaronson-Artikel zu diesem Thema verfasst, sie ist jedoch nicht in englischer Sprache. Siehe das Originalpapier .

Persönlich habe ich von einem anderen Beispiel eines realen Problems gehört, das in der Berechnung modelliert ist. Die Arbeit befasst sich mit Kontrollsystemmodellen, die auf Vogelschwärmen basieren. Obwohl es im realen Leben für Vögel nur eine kurze Zeit dauert, ist es unlösbar ("ein Turm aus zwei"), wenn es als Rechenproblem analysiert wird. Siehe das Papier von Bernard Chazelle für Details.

[Bearbeiten: Der Teil über das Chazelle-Papier wurde präzisiert. Vielen Dank für die genaue Angabe.]

Chazisop
quelle
2
nicht nur exponentiell. Es ist eigentlich ein Turm von 2s.
Suresh Venkat
1
Suresh ist natürlich richtig. Darüber hinaus ist das Chazelle-Papier keine Analyse der Vogelbeflockung: Es ist eine Analyse bekannter Kontrollsystemmodelle, die auf der Vogelbeflockung basieren. Insbesondere erfordert seine Analyse die Anwendung einer "Hystereseregel", nach der Vögel nicht beobachtet werden, dass sie sich selbst gehorchen. Weitere Informationen zu diesem Forschungsprogramm finden Sie in Chazelles Kommentar Nr. 3 hier .
Aaron Sterling
0

Ich stimme immer noch für das N-Körper-Problem als Beispiel für NP-Unlösbarkeit. Die Herren, die sich auf numerische Lösungen beziehen, vergessen, dass die numerische Lösung ein rekursives Modell ist und im Prinzip keine Lösung wie eine analytische Lösung. Die analytische Lösung von Qui Dong Wang ist unlösbar. Proteine, die sich falten können, und Planeten, die in Systemen mit mehr als zwei Körpern umkreisen können, sind physikalische Systeme und keine algorithmischen Lösungen, wie sie das P-NP-Problem anspricht.

Ich muss auch die Schwierigkeiten von Chazisop mit Lösungen in ununterbrochener Zeit schätzen. Wenn entweder Zeit oder Raum kontinuierlich sind, werden potenzielle Zustandsräume unzählbar (aleph eins).

James McIntosh
quelle
2
Das exakte / analoge 3-Körper-Problem ist nicht nur NP-schwer; es ist unentscheidbar . Auf der anderen Seite sind echte physikalische Systeme nicht wirklich analog. Sie haben gerade eine mathematische Abstraktion durch eine andere ersetzt.
Jeffs
-1

n


quelle
2
Das ist nicht wahr. Wir können das n-Körper-Problem tatsächlich effizient lösen, es gibt einfach keine analytische Lösung. Numerische Methoden funktionieren einwandfrei.
Joe Fitzsimons
6
Genau. Ich habe noch nie gesehen, dass ein Planet eine analytische Lösung für das n-Körper-Problem aufweist, daher ist der Vergleich unfair.
Robin Kothari