Konsens über P = NP in einer Welt mit RP = NP

12

wird allgemein als falsch vermutet.RP=NP

Aber stell dir für einen Moment vor, dass es wahr ist. Wie wahrscheinlich wäre es in diesem Fall, dass ?P=NP

Mit anderen Worten: Was könnte in einer Welt, in der , noch als Hindernis für uns angesehen werden, P = N P zu glauben ?RP=NPP=NP

cc.complexity-theory complexity-classes conditional-results Giorgio Camerani
quelle
3
Mit anderen Worten, Sie fragen nach einem Orakel, für das RP = NP, aber P NP gilt. ≠
Yuval Filmus
Ja. Ich möchte wissen, ob in einer Welt mit die zusätzlichen Bedingungen, die für P ≠ N P gelten müssen, strenger und unwahrscheinlicher sind als die zusätzlichen Bedingungen, die für P = N P gelten müssen . RP=NPP≠NPP=NP
Giorgio Camerani
7
@Yuval Filmus: Ich weiß nicht, ob es sich um eine Relativierungsbarriere handelt, aber wenn ja, dann gibt es ein Orakel, in Bezug auf das RP = EXP (was impliziert, dass P ≠ RP = NP ist). Ich kann den Hinweis für diese Tatsache jetzt nicht finden, aber er wird in der Bemerkung nach Theorem 6 in Heller 1986 mit Verweisen auf zwei Arbeiten von Kurtz und Heller, beide in der Abhandlung von "Conference on Computational Complexity Theory" im März 1983, angegeben.
Tsuyoshi Ito

Antworten:

14

Ehrlich gesagt denke ich nicht, dass Stack Exchange ein geeigneter Ort ist, um nach einer zukünftigen Vorhersage zu fragen. Trotzdem werde ich eine Antwort posten, weil es Spaß macht, mit der Idee des Wahrsagens zu spielen.

Soweit ich weiß, wurde die Möglichkeit von P ≠ RP = NP nicht ausgeschlossen. Darüber hinaus gibt es eine Sprache A mit RP A = EXP A [Hel83, Kur83], was unmittelbar impliziert, dass P A ≠ RP A = NP A ist . (Ich habe weder [Hel83] noch [Kur83] angekreuzt und das Ergebnis und die Verweise aus der Bemerkung nach Satz 6 in [Hel86] entnommen.) Mit anderen Worten, selbst der Beweis der Implikation RP = NP ⇒ P = NP erfordert a nichtrelativierende Technik, und daher ist es verständlich, dass diese Implikation nicht bewiesen wurde.

(Lance Fortnow hat ein ähnliches Ergebnis im Computational Complexity-Blog diskutiert: Oracle-Ergebnisse sind gut für Sie .)

Wenden wir uns nun der Wahrsagerei zu.

Wie viel sagt dieses Orakelergebnis über die Wahrscheinlichkeit von P = NP in der Welt aus, in der RP = NP bereits bewiesen wurde? Nicht viel. Zumindest sollte dies nicht als Beweis dafür gewertet werden, dass es in der Welt, in der RP = NP nachgewiesen wurde, wahrscheinlich immer noch schwierig ist, P = NP nachzuweisen. In einer solchen Welt sind dem Menschen einige neue, leistungsfähige nichtrelativierende Techniken bekannt, und daher wäre es nicht sinnvoll, „erfordert eine nichtrelativierende Technik“ als Beweis für Schwierigkeiten zu interpretieren.

Allgemein gesprochen, wenn RP = NP trotz aller Überzeugungen (und auch Beweistechniken) dagegen bewiesen wurde, ist unser derzeitiges intuitives Verständnis über effizientes Rechnen wahrscheinlich sehr falsch. Offensichtlich können wir unsere gegenwärtige Intuition nicht auf die Vernunft über die Welt anwenden, in der unsere gegenwärtige Intuition spektakulär versagt. Ich glaube nicht, dass wir eine fundierte Vermutung über eine solche Welt anstellen können, es sei denn, dies wurde rigoros bewiesen.

Verweise

[Hel83] Hans Heller. Auf relativierten Polynomhierarchien, die sich auf zwei Ebenen erstrecken. In Proceedings of Conference on Computational Complexity Theory , S. 109–114, UC Santa Barbara, März 1983.

[Hel86] Hans Heller. Auf relativierten exponentiellen und probabilistischen Komplexitätsklassen. Information and Control , 71 (3): 231–243, Dezember 1986. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] S. Kurtz (Stuart A. Kurtz?). Die Feinstruktur von NP: Relativierungen. In Proceedings of Conference on Computational Complexity Theory , S. 42–50, UC Santa Barbara, März 1983.

Tsuyoshi Ito
quelle
"Offensichtlich können wir unsere gegenwärtige Intuition nicht auf die Vernunft über die Welt anwenden, in der unsere gegenwärtige Intuition spektakulär versagt" ... das ist eine große Aussage.
T ....