Welche Beziehung besteht zwischen P vs. NP und der Fähigkeit der Natur, NP-Probleme effizient zu lösen?

Ich habe darüber nachgedacht, wie die Natur lächerliche (dh NP) Probleme mit Leichtigkeit effizient berechnen kann. Zum Beispiel benötigt ein Quantensystem einen Elementvektor, um den Zustand darzustellen, wobei nur die Anzahl der Teilchen ist. Die Natur braucht keine zusätzliche Zeit, obwohl dieses Teilchen-System exponentiell "gelöst" wird.$2^n$$n$$n$

Dies mag keine völlig gültige Annahme sein, aber das Aktionsprinzip in der Physik lässt mich denken, dass die Natur die Dinge immer auf einfachste Weise tun will. Wenn das nicht stimmt, ist diese Frage wahrscheinlich umstritten.

Wenn wir festgestellt haben, dass die Natur einige Probleme NICHT effizient lösen kann, bedeutet dies, dass wir dazu verdammt sind, NP-Probleme in Polynomzeit lösen zu können? Sind die Gesetze der Physik eine Waffe, die stark genug ist, um P gegen NP zu bekämpfen? Ist die Umkehrung der ersten Frage / Behauptung auch wahr (wenn die Natur dies kann, muss es auch für uns einen Weg geben)?

Hier sind fünf Anmerkungen, die für Sie hilfreich sein könnten:

1. Die derzeitige Überzeugung ist , dass trotz der Exponentialität der Wellenfunktion, die Quantenmechanik wird nicht uns NP-vollständige Probleme in Polynomialzeit lassen lösen (obwohl es bekanntlich nicht bestimmte „besondere“ NP - Probleme, wie Factoring und diskreter Logarithmen lassen Sie uns lösen). Die grundlegende Schwierigkeit besteht darin, dass selbst wenn eine Lösung für ein NP-Problem "irgendwo" in der Wellenfunktion liegt, dies nicht sinnvoll ist, wenn eine Messung diese Lösung nur mit exponentiell geringer Wahrscheinlichkeit ergibt. Um einen nützlichen Quantenalgorithmus zu erhalten, müssen Sie Quanteninterferenz verwenden, um die richtige Antwort mit hoher Wahrscheinlichkeit zu erhalten, und es ist nur bekannt, wie Sie auf diese Weise (im Vergleich zum bekanntesten klassischen Algorithmus) für einige spezielle Probleme eine exponentielle Beschleunigung erzielen können wie Factoring.

2. Das Aktionsprinzip impliziert nicht, dass die Natur magische Minimierungskräfte besitzt. Der einfachste Weg, dies zu erkennen, besteht darin, dass jedes physikalische Gesetz, das im Sinne des Aktionsprinzips formuliert ist, auch im Sinne der gewöhnlichen zeitlichen Entwicklung eines Zustands formuliert werden kann , ohne dass darauf hingewiesen wird, dass etwas minimiert wird.

3. Wenn P = NP, können NP-vollständige Probleme in der Polynomzeit des physischen Universums sicherlich gelöst werden, da universelle Turing-Computer existieren (Sie verwenden jetzt einen). Die umgekehrte Richtung ist jedoch alles andere als offensichtlich! Selbst wenn Sie beispielsweise P ≠ NP annehmen, ist es logisch immer noch möglich (wenn auch sehr unwahrscheinlich), dass Quantencomputer NP-vollständige Probleme in Polynomzeit lösen könnten.

4. Die bloße Annahme, dass es einige Probleme gibt, die wir nicht effizient lösen können, bedeutet sicherlich nicht, dass NP-vollständige Probleme zu diesen Problemen gehören müssen! (Vielleicht stellt sich heraus, dass wir mit der Quantengravitation NP-vollständige Probleme in linearer Zeit lösen können, aber die PSPACE -vollständigen Probleme brauchen immer noch exponentielle Zeit ... :-D)

5. Was auch immer es wert ist, mein Geld basiert auf der Vermutung, dass nicht nur P ≠ NP, sondern auch NP-vollständige Probleme im physischen Universum nicht zu lösen sind - mit Quantencomputern, analogen Computern, "Schwarzen Loch-Computern" oder anderen andere Ressource. Weitere Informationen zu meinen Gründen finden Sie in meinem alten Umfrageartikel NP-vollständige Probleme und physische Realität

Diese Frage bezieht sich im Wesentlichen auf das Gebiet des natürlichen Rechnens, das viele interessante Winkel / Richtungen hat. Hier ist ein schöner Übersichtsartikel: Grundlagen des Natural Computing: Ein Überblick von de Castro.

Auch diese Bereiche sind grundsätzlich offene Fragen im Bereich Computer und Physik und unterliegen einem inhärenten "Unsicherheitsprinzip", da sie aus verschiedenen Gründen möglicherweise nie endgültig beantwortet werden können. Es gibt viele verschiedene physikalische Rechensysteme, neue werden im Laufe der Zeit entdeckt (z. B. DNA-Computing ist ein relativ junges Gebiet), und wir können nicht sicher sein, dass wir sie alle gefunden haben [und aus Erfahrung / Geschichte ist es unwahrscheinlich, dass wir sie haben].

auch die extremen Grenzen der Physik sind anwendbar [zB für Schwarze Löcher usw.] und diese dehnen die Theorien der Physik bis an die Grenzen aus! (siehe z. B. "Was ist das Informationsvolumen?" ) Theoretische Physiker erkennen im Allgemeinen an, dass es Aspekte der physischen Realität gibt, die nicht durch menschliches Wissen und [mathematische] Modelle abgedeckt werden, insbesondere an den Extremen.

Es gibt jedoch einige stark vertretene / verteidigte, möglicherweise unbeweisbare Überzeugungen unter Forschern, so dass sie im gleichen Sinne wie die Church-Turing-These als "Thesen" bezeichnet werden könnten. [1] Einige Behörden beziehen sich auf eine Church-Turing-These zur Polynomzeit, die sich auf Ihre Frage (n) bezieht. Es gibt auch Hinweise auf die Strong CT-These:

Jedes Computergerät kann von TMs mit im schlimmsten Fall einer Polynomverlangsamung simuliert werden.

oder die Extended CT These [Parberry] [3]:

Die Zeit bei allen "vernünftigen" Maschinenmodellen wird durch ein Polynom in Beziehung gesetzt.

Kurz gesagt, die Forschung und das Schreiben in diesem allgemeinen Bereich sind nicht geregelt. es ist aktiv / andauernd und unterliegt hohen Kontroversen. Es gibt einige Hinweise auf Wikipedia [4], aber ansonsten haben wir keinen schönen Übersichtsartikel zu diesem Thema gesehen, sondern nur viele verschiedene Artikel, die dazu neigen, bestimmte Standpunkte zu vertreten. Beachten Sie auch, dass es im Bereich der QM-Datenverarbeitung derzeit eine sehr starke Debatte / Kontroverse über Machbarkeit (inhärentes Rauschen) und Lebensfähigkeit usw. gibt. [5]

[1] Physik und die Church-Turing-These mathoverflow

[2] Was würde es bedeuten, die CT-These cstheory.se zu widerlegen ?

[3] erweiterte CT-Arbeit cstheory.se

[4] Variationen der Church-Turing-These , Wikipedia

[5] Stand der Technik und Perspektiven für QM-Computing Dyakonov

Ich hatte einmal einen Professor für neuronale Berechnungen, der ein hervorragendes Beispiel dafür aufzeigte, wie "analoge" Techniken bei peinlich parallelen Problemen eingesetzt werden können, um die asymptotische Grenze einer Berechnung zu verringern:

Nehmen Sie ein Bündel Stöcke unterschiedlicher Größe. Es gibt viele algorithmische Möglichkeiten, um dieses Bündel von Sticks mit O (n * log (n)) vom längsten zum kürzesten zu sortieren. Eine "analoge" Möglichkeit, dieses Bündel von Stöcken zu sortieren, besteht darin, sie auf ein Ende zu stellen und die Stöcke an einem Ende auf einem Tisch ruhen zu lassen (1 Schritt). Jetzt haben Sie alle Stöcke mit einem Ende auf gleicher Höhe am Tisch. Nehmen Sie Ihre Hand und legen Sie sie darauf - sie trifft am längsten, entfernen Sie den Stock und wiederholen Sie den Vorgang für N Schritte. Dieser Prozess ist O (N + 1), was O (N) ist. Der Schlüssel hier war das Stapeln der Sticks am Ende - eine massiv parallele Lösung, um die anderen Enden der Sticks entlang der z-Achse (nach oben) zu ordnen.

Dies ist ein ordentliches Gedankenexperiment und kann eine Vorstellung davon geben, wie analoge Lösungen auf einfache Weise die asymptotische Grenze eines Algorithmus reduzieren können. Zwei große Einschränkungen hier:

1) Wir haben mit diesem Beispiel kein NP-Problem zu einem P-Problem gemacht (dazu später mehr) und

2) Wenn Sie N Prozessoren zum Sortieren von N Elementen verwendet haben, können Sie die Zahlen in O (log n) -Zeit (mit einer großen Konstante) sortieren, sodass die Reduzierung nicht magisch ist. Manchmal sind die benötigten analogen Ressourcen, die ein Problem auf sehr parallele Weise lösen, billig. Ein weiteres Beispiel für eine billige Ressource wären Neuronen (biologisch) für komplexes Lernen und Mustererkennung.

Neuronen können auch den scheinbaren NP => P relativieren. NP-Probleme sind NP, um die optimale Lösung zu finden . Sie können in P-Zeit eine "gut genug" Lösung finden, die in der Natur gut funktioniert. Evolution wählt hocheffiziente Lösungen, die "gut genug" sind. Überlegen Sie, wie gut die durchschnittliche Person Objekte in fast O (1) Zeit identifizieren kann. Das liegt daran, dass viel parallel verarbeitet wird und Ihr Gehirn immer noch nicht immer die optimale Lösung findet. Zum Beispiel optische Täuschungen oder das Vergessen, wo Sie Ihre Schlüssel ablegen (was für einen Computer leicht O (1) wäre!).

Ein weiterer Punkt mit NP vs P in der Natur: Das Lösen von NP, um die optimale Lösung zu finden, ist nicht dasselbe wie das Identifizieren der optimalen Lösung. Die Identifizierung einer optimalen Lösung für ein NP-Problem kann in P-Zeit erfolgen. Wiederum funktioniert die Erkennung einer "gut genug" -Lösung eher als eine optimale Lösung. Nehmen wir das Beispiel der Proteinfaltung - dies ist ein Beispiel für die Natur, die all das tut. Es nutzt molekulare Wechselwirkungskräfte, die alle parallel arbeiten (es ist nicht erforderlich, dass der natürliche Faltungsalgorithmus wie ein Rechenalgorithmus jeweils ein Atom adressiert). Es gibt auch keine Garantie dafür, dass die (funktional) optimale Lösung für die Proteinfaltung gefunden wird.

Es gibt viele Beispiele für Krankheiten aufgrund von Proteinfehlfaltung. Wie @PeterShor betonte, funktioniert der "natürliche" Algorithmus manchmal überhaupt nicht (was zu einer thermodynamisch optimalen Lösung führt, aber nicht zu einer funktionalen). Hier kommen Chaperonproteine ​​ins Spiel - sie leiten die Faltung in die richtige funktionelle Form (ein thermodynamisches Lokal)Minimum). Richtig gebildete Proteine ​​interagieren auch mit anderen Proteinen, um sie an den richtigen Ort zu transportieren, so dass die "schlechten" (bei denen der heuristische Algorithmus das NP-Problem nicht wirklich gelöst hat) häufig abgebaut werden, ohne irgendwohin transportiert zu werden. Alle diese Transporte und Faltmechanismen finden mit massiven parallelen Rohren statt. Mehrere Transkriptions- und Verarbeitungsmechanismen wandeln gleichzeitig DNA-> RNA-> Protein an verschiedenen Punkten einer Gensequenz um. Jede Zelle in Ihrem Körper tut dasselbe (aber mit unterschiedlichen chemischen Botschaften darüber, was produziert werden soll).

Kurz gesagt: Wie macht die Natur das? Tricks und Parallelität. Im Allgemeinen verwandelt es ein NP-Problem nicht in P, sondern lässt es einfach aussehen.