Determinismus und P=NP

Dieser hat mir schon seit einiger Zeit den Kopf zerbrochen. Soweit uns die Physik derzeit sagt, leben wir in einer Welt, in der die physikalischen Gesetze induktiv, aber nicht deterministisch sind, weil es auf einer zugrunde liegenden Ebene das gibt, was wir für echte Zufälligkeit halten.

Stellen wir uns also eine Welt vor, in der alles perfekt deterministisch ist, es gibt keine zugrunde liegende Zufälligkeit. Daher kann jeder physikalische Prozess jedes Mal exakt durch einen deterministischen Algorithmus gelöst werden. Ist in einer solchen Welt P = NP? Wenn wir uns eine solche Welt vorstellen können, ist P = NP? Oder sind die beiden Konzepte des Determinismus in Informatik und Physik gar nicht verwandt? Es muss zumindest eine Verbindung geben. Bitte keine Ein-Wort-Antworten, ich möchte hier einen Einblick.

Antworten (4)

Abstrakte Mathematik muss nicht mit Physik verwandt sein. Es gibt viele Dinge, die Mathematiker routinemäßig berücksichtigen (wie nicht messbare Mengen usw.), die unmöglich in der physikalischen Welt existieren können.

Insbesondere haben die Gesetze der physikalischen Welt keinen Einfluss auf das P=NP-Problem.

Hinzu kommt, dass der in der Computational Complexity Theory verwendete Nichtdeterminismus mathematisch definiert ist. Die Frage, ob die Klasse P dieselbe ist wie die Klasse NP, ist eine mathematische. Sie ist allein durch mathematische Überlegungen entscheidbar. Ein deterministischer Algorithmus für ein Problem in NP könnte nachweislich exponentiell Zeit benötigen (oder auch nicht, wir wissen es noch nicht, weil es keinen mathematischen Beweis gibt!).
Ich bin mir nicht sicher, ob Ihr letzter Satz richtig ist; Berechenbarkeit ist eine abstrakte Idee, während die praktische Berechenbarkeit durch die uns bekannten physikalischen Gesetze bestimmt wird. Ob P = NP oder nicht, scheint etwas über die physikalische Realität zu sagen. Betrachten Sie die Leistungsfähigkeit des menschlichen Gehirns: Löst es NP-vollständige Probleme? Wir wissen es nur noch nicht; wenn ja, ist das ziemlich interessant. Wenn dies nicht der Fall ist, findet es immer einen Weg zum "Betrügen", indem es domänenspezifische Informationen berücksichtigt, um das Problem nach P zu verschieben? Sind alle "interessanten" Fragen irgendwie auf weniger als NP reduzierbar oder klein genug?
@labreuer, Sie gehen von menschlichen Gehirnkräften aus, die es möglicherweise nicht hat. Es stimmt, viele interessante Probleme, einschließlich derjenigen, die von unserem Gehirn angegangen werden, sind NP-schwer, aber wer hat Ihnen gesagt, dass wir gut darin sind, Lösungen für sie zu finden? Meistens reicht eine Näherungslösung für praktische Zwecke aus, und viele NP-schwere Probleme haben P-Näherungen (obwohl nicht alle). Außerdem reicht es für praktische Zwecke manchmal aus, „deutlich öfter richtig als falsch“ zu liegen, was die Komplexitätsklasse BPP relevanter macht als P.
@Michael, sehr wahr. Vielleicht haben alle interessanten NP-vollständigen Probleme ausreichend gute Näherungen, sobald das gesamte Domänenwissen genutzt wird. Die Aussage, dass Physik und Berechnung völlig getrennt sind, erscheint mir jedoch fadenscheinig. Wenn zukünftige physikalische Arbeiten die Berechnungstheorie informieren können, würde ich behaupten, dass es eine Art Verbindung gibt. Ich habe eine Antwort auf diese Frage angeboten, die meine Position ein wenig konkretisiert.
@labreuer: Nicht alle NP-vollständigen Probleme haben eine Annäherung, die aus dem PCP-Theorem folgt. Unabhängig davon bedeutet Nichtdeterminismus in der Komplexitätstheorie nicht genau dasselbe wie in der Philosophie; das macht das P v. NP-Problem für die Physik weniger relevant.
@Michael, deshalb habe ich gesagt "sobald das gesamte Domänenwissen genutzt wird". :-p Vielleicht haben alle Fragen, die wir beantworten müssen, um die Realität weiter zu erforschen, gute Annäherungen – es wäre enttäuschend, wenn wir aufgrund einer bloßen Rechenbarriere auf einem bestimmten Fortschrittsniveau „stecken bleiben“. Was die Verbindung zwischen Berechnung und Physik betrifft, denke ich, dass es eine offene Frage ist, ob es eine tiefe Verbindung gibt. Ich glaube zufällig, dass unsere Welt eine Verdinglichung eines bestimmten formalen Systems ist. Das macht das „Abstrakte“ nicht so weit weg, wie manche denken. Wer hat Recht? Ich bin mir nicht sicher, ob wir es wissen!

Ein deterministisches Universum ist möglicherweise kein Quantenuniversum, in diesem Fall wären Algorithmen wie Shors Algorithmus unmöglich; ob es eine Quanten- oder Post-Quanten-Methode zur Lösung von NP-Problemen in P-Zeit geben wird, ist unbekannt. Angenommen, es gibt. Das bedeutet nicht, dass P = NP; Shors Algorithmus gehört zur Komplexitätsklasse BQP : Bounded Error Quantum Polynomial Time.

Die NP-Komplexitätsklasse ist eine andere Art von nicht deterministisch als unser aktuelles Wissen über die Quantenmechanik und ihre nicht deterministische Natur. Wir wissen das, weil kein bekannter Quantencomputer NP-vollständige Probleme in polynomieller Zeit lösen kann. Denn um NP-vollständige Probleme in P-Zeit zu lösen, müssten Sie in der Lage sein, n – 1 neue Instanzen des Programms an jedem Entscheidungspunkt mit n möglichen Entscheidungen hervorzubringen. Es ist nicht ganz "alles gleichzeitig auszuprobieren", aber es ist nah dran. Kein bekannter Quantencomputer kann „alles auf einmal ausprobieren“; Das liegt daran , dass Quantenschaltkreise nicht „leistungsfähig genug“ sind.

Angenommen, wir finden eine neue Art von Quantencomputer, der NP-vollständige Probleme in P-Zeit lösen kann. Ob das Universum so sein musste oder nicht , wird wohl eine Frage der Philosophen sein. Aber Sie können sicherlich sehen, dass in einem deterministischen Universum dieser Quantencomputer [wahrscheinlich] nicht verfügbar wäre. Wenn Sie also eine digitale Welt erschaffen, die von fühlenden Wesen bevölkert ist, und diese Welt deterministisch machen, werden diese Wesen wahrscheinlich nicht in der Lage sein, in einem bestimmten Zeitraum so viel zu berechnen wie Sie.

Abgesehen davon könnte sich herausstellen, dass klassische Computer verwendet werden können, um NP-Probleme in P-Zeit zu lösen, wenn am Ende P = NP ist. In diesem Fall wäre es völlig irrelevant, ob die Welt deterministisch oder indeterministisch ist oder nicht. An diesem Punkt wissen wir es einfach nicht. Wenn Sie in Bezug auf Berechnung und Physik umgehauen werden möchten, sehen Sie sich diese Einführung zur Berechnung von Schwarzen Löchern an und gehen Sie dann zu Scott Aaronsons Erörterung der jüngsten Firewall-Kontroversen über . "Was ist in unserem Universum realistisch berechenbar?" ist eine spannende Frage. Vielleicht gibt es eine tiefe Verbindung zwischen Berechnung und Physik!

Die Frage, ob P = NP ist, hat keinen Einfluss darauf, ob Prozesse deterministisch sind, sondern nur auf den relativen Aufwand , den deterministische gegenüber nichtdeterministischen schrittweisen Prozessen erfordern können, um zu Lösungen für bestimmte Arten von Problemen zu gelangen. Der betrachtete Nichtdeterminismus ist immer auf eine endliche, aufzählbare Auswahl an Alternativen beschränkt, sodass für jeden der betrachteten nichtdeterministischen Prozesse immer ein deterministisches „Äquivalent“ existiert (z. B. erhalten durch erschöpfendes Ausprobieren aller Alternativen auf irgendeine systematische Weise).

In einfachen Worten sagt Michael, dass sich die Fragen der Mathematik (wie P = NP) nicht auf die Eigenschaften irgendeiner physikalischen Welt beziehen. Die Physik verwendet und entwickelt die Mathematik, die Mathematik nimmt keine physikalischen Beobachtungen oder Einsichten als Input.

Determinismus und P=NP
AntwortenHierDatenschutz-Bestimmungen1y, 0v