ist ?

8

Ich denke, dass diese beiden Klassen gleich sein sollten, aber ich kann keine Literatur dazu finden und habe einen begrenzten Hintergrund zu diesem Thema.

Dies ist meine Argumentation, und ich würde gerne wissen, ob (1) dies bereits bekannt ist oder (2) ich etwas falsch verstanden habe oder (3) ich gerade etwas Nützliches herausgefunden habe:

P.C.T.C. ist die Klasse von Problemen, die gelöst werden können, indem polynomielle Datenmengen in eine Zeitmaschine gestellt werden.

B.P.P.peinth ist die Klasse von Problemen, die durch Nachauswahl in einer probabilistischen Turing-Maschine gelöst werden können, dh Fälle ignorieren, die Sie nicht interessieren.

P.C.T.C.⊆B.P.P.peinth da Sie eine geschlossene zeitähnliche Kurve mit folgender Nachauswahl simulieren können: Scannen Sie am Anfang das gesamte Programm, sowohl den Status als auch den Speicher. Führen Sie dies nach der Verarbeitung erneut aus und wählen Sie erneut aus, sodass Sie nur zurückkehren, wenn der Status und der Speicher jetzt genau dem Startstatus und dem Speicher entsprechen (mit Ausnahme eines einzelnen Bits, das angibt, ob dies die erste Iteration ist oder nicht, um eine zu verhindern Endlosschleife).

B.P.P.peinth⊆P.C.T.C. da Sie die Nachauswahl wie folgt simulieren können: Wenn die Nachricht aus der Zukunft mit1 beginnt, senden Sie die Nachricht0 in die Vergangenheit. Ansonsten verfahren Sie wie gewohnt. Wenn Sie zu dem Schritt gelangen, bei dem Sie normalerweise nachträglich auswählen würden, senden Sie eine 1 in die Vergangenheit iff. Sie möchten diese Zeitleiste ignorieren, andernfalls eine0 . Die einzige konsistente Version ist jetzt die, bei der Sie beide eine 0 empfangen und senden, weil Sie mit den Ergebnissen zufrieden waren.

complexity-theory complexity-classes quantum-computing Florian Dietz
quelle
2
Ich habe absolut keine Ahnung von diesem Thema, aber in diesem Papier Link sie sagen , dass die Klasse P_CTC zu PSPACE gleich ist und BPP_PATH gleich POST_BPP , die in P mit einem NP Orakel enthalten ist. Also sind die beiden Klassen wahrscheinlich nicht gleich
Rotia
Das ist gut zu wissen! Ich würde nicht sagen, dass dies zeigt, dass die beiden Klassen nicht gleich sind: Es bedeutet nur, dass PSPACE = P ^ NP ist, wenn sie gleich sind. Es macht es weniger wahrscheinlich, dass es wahr ist, weil jemand anderes diese Verbindung früher hätte entdecken können, wenn es wahr wäre, aber es bedeutet auch, dass der IF-Ansatz korrekt ist, dann hat dies nützliche Konsequenzen.
Florian Dietz
Die Skizze Ihres Beweises, dass "P_CTC in BPP_PATH ist", ist meiner Ansicht nach der Schuldige. Ein Problem ist, dass es nicht offensichtlich ist, wie Ihr Post-BPP-Computer konsistente Zustände der Polynomzahl der CTC-Register ordnungsgemäß beibehält. P_CTC ist nicht einfach eine Polynomzeit mit Zeitreise. Es gibt sehr spezifische kausale Konsistenzkriterien, die durchgesetzt werden müssen. Diese Einschränkungen geben der Maschine die Möglichkeit, teilweise feste Punkte leicht zu finden, was wohl allgemeiner ist als die bloße Nachauswahl. Ich ermutige Sie, die formale Definition von P_CTC sorgfältig zu überdenken.
Mdxn

Antworten:

0

Ich glaube, ich habe die Antwort gefunden: Der Beweis ist falsch. BPP_PATH ist nicht in P_CTC enthalten, da P_CTC eine einzige eindeutige Antwort geben muss, während BPP_PATH ein probabilistischer Algorithmus ist, sodass die zweite Reduktion nicht funktioniert. Damit es funktioniert, müsste man die Zeitreiseinformationen verwenden, um die Anzahl der Erfolge des probabilistischen Algorithmus gegenüber der Anzahl seiner Fehler zu zählen. Ich habe keine Ahnung, wie das geht oder ob es überhaupt geht (wahrscheinlich nicht).

Florian Dietz
quelle
... und fünf Minuten später bin ich mir nicht mehr sicher. P_CTC = PSPACE, und kann PSPACE BPP nicht simulieren?
Florian Dietz
2
Sie verwirren sich. Deterministische Maschinen sind grundsätzlich probabilistische Maschinen ohne Fehlertoleranz und ohne Zugang zur Zufälligkeit. Wenn ein Kandidat die gleichen Fragen ohne Fehler beantworten kann, gibt es kein Problem. Es besteht keine Notwendigkeit, genauso oft falsch zu liegen. Unabhängig davon können Sie mit PSPACE eine BPP-Maschine einfach simulieren, indem Sie jede zufällige Zeichenfolge testen und die Akzeptanzwahrscheinlichkeit manuell berechnen können. Da P_CTC = PSPACE ist, gibt es eine äquivalente P_CTC-Maschine, die bei einer bestimmten BPP-Maschine auf die gleiche Weise antworten kann.
Mdxn