Beweise, Barrieren und P vs NP

25

Es ist allgemein bekannt, dass jeder Beweis, der die P-gegen-NP- Frage löst , Relativierung , natürliche Beweise und Algebrierungsbarrieren überwinden muss. Das folgende Diagramm unterteilt den "Proof Space" in verschiedene Regionen. Beispielsweise entspricht der Menge von Beweisen, die relativieren und naturalisieren. (Geometric Complexity Theory) ist natürlich die rein äußere Region. $RN$ $GCT$

Nennen Sie einige Beweise zusammen mit den bekanntesten Regionen, zu denen sie gehören. Platzieren Sie sie optimal, dh wenn bekannt ist, dass ein Beweis relativiert, naturalisiert und algebrisiert, sollte er nicht nur in sondern auch in platziert werden . Wenn ein Beweis relativiert, aber nicht naturalisiert, gehört er zu und so weiter. $RNA$ $RN$ $R$ ${\setminus}$ $N$

Alt-Text

cc.complexity-theory proofs barriers p-vs-np Shiva Kintali
quelle

Aber gibt es überhaupt bekannte gültige Beweise für P gegen NP?

gphilip

2

Ich denke jedoch, dass dies eine klassische CW-Frage ist.

Suresh Venkat

@gphilip Es handelt sich um Beweise für die Komplexitätstheorie im Allgemeinen.

Shiva Kintali

@Suresh Das Platzieren von Proofs in diesen Regionen ist höchst nicht trivial. Personen, die Antworten veröffentlichen, sollten für ihr Wissen und Verstehen dieser Hindernisse belohnt werden (natürlich durch Mehrstimmen). Was denkst du ?

Shiva Kintali

Nachdem ich die Antwort von Suresh unten gelesen habe, habe ich die Frage (korrigiere mich, wenn ich mich irre): Sie suchen nach Klassifikationen der Form "Wenn ein Beweis, der P gegen NP auflöst, die Eigenschaft X hat, dann gehört er zur Region Y in der Bild." In Sureshs Antwort ist X "Interaktiv" und Y liegt außerhalb von R, möglicherweise auch außerhalb von N.

Gphilip

17

Ich denke, Sie müssen Ihr Venn-Diagramm neu zeichnen ... jede Eingrenzung von Komplexitätsklassen, die relativiert, wird auch algebriert, zumindest im Sinne von Aaronson und Wigderson. Das heißt, der Zugriff auf die "niedriggradige Erweiterung" eines Orakels ist nur leistungsfähiger als der Zugriff auf das Orakel. In ähnlicher Weise impliziert jedes Orakel, das zeigt, dass eine Trennung "nicht-algebrisierende" Techniken erfordert, dass auch "nicht-relativierende" Techniken erforderlich sind.

Ryan Williams
quelle

R \subseteq A

$R \subseteq A$

4

Was Ryan sagt, gilt nur für die Eindämmung. Ein Ergebnis wie P = NP impliziert, dass P = PH relativiert, aber nicht algebriert.

Lance Fortnow

@Lance: Danke für die Klarstellung. Es ist also sinnvoll, das Diagramm unverändert zu lassen.

Shiva Kintali

3

P^{\tilde{A}} = N P^{\tilde{A}}

$P^{\tilde{A}} = NP^{\tilde{A}}$

P H^{A} \subseteq P^{\tilde{A}}

$PH^{A} \subseteq P^{\tilde{A}}$

13

Entgegen früherer Behauptungen in diesem Thread ist nicht bekannt, dass Algebrisierung im Sinne von Aaronson & Wigderson die Relativierung subsumiert. Beispielsweise,

\begin{matrix} (†) & (\exists C : C \subset N E X P \land C ⊄ P / p o l y) ⟹ N E X P ⊄ P / p o l y \end{matrix}

$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$

ist eine relativierende Aussage. (Tatsächlich hat es einen relativierenden Beweis, was auch immer das für den Leser bedeuten mag.) Es ist jedoch nicht bekannt, dass es algebrisiert wird, wie dies von Aaronson & Wigderson selbst in Abschnitt 10.1 ihrer Arbeit [1] angedeutet wurde. (Während AW uns sagt, dass in der obigen Grafik außerhalb von liegen muss , ist es denkbar, dass liegt drin!) $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $\mathrm {A}$ $\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$

Eine kürzlich erschienene Arbeit von Eric Bach und mir [2] liefert jedoch eine Formulierung der Algebrisierung, die die Relativierung subsumiert. Wenn wir den AW-Begriff eines algebraischen Orakels - bezeichnet als für eine Sprache - nehmen und ihn mit Bedacht modifizieren, können wir die Pathologien wie oben eliminieren . $\tilde O$ $O$ $(\dagger)$

Das Fazit ist, dass Algebrisierung, wenn geeignet definiert, Relativierung in Bezug auf ein algebraisches Orakel ist - eine algebraische Relativierung, bei der jedes Orakel ein "Wackeln" bekommt, was ist die leere Menge im obigen Diagramm, daher auch . $\mathrm{R} \setminus \mathrm{A}$ $\mathrm{RN}$

[1] http://www.scottaaronson.com/papers/alg.pdf
[2] http://eccc.hpi-web.de/report/2016/040/

PS: Eine andere Formulierung für die Algebrisierung wurde von Impagliazzo, Kabanets und Kolokolova früher vorgeschlagen, die ebenfalls in einfügt, von der jedoch bekannt ist, dass sie nicht so mächtig ist wie der AW-Begriff. Siehe meine Arbeit mit Eric zum Vergleich. $\mathrm{R}$ $\mathrm{A}$

Barış Aydınlıoğlu
quelle

Vielen Dank, Baris. Ich bin froh, dass endlich jemand den Begriff der Algebrisierung gefunden hat, der formal das tut, was wir denken, dass es sollte :)

Ryan Williams

11

Die Zeit- und Raumhierarchiesätze relativieren sich. Sie sind einheitlich und scheinen sich nicht zu naturalisieren.

Ich denke, dass indirekte Diagonalisierung Ergebnisse wie die TimeSpace-Untergrenzen von Lance Fortnow et al. und auch das Ergebnis von Ryan Williams relativiert sich nicht, weil sie keine Black Box sind (aber ich bin mir nicht sicher). Die Beweise scheinen sich nicht zu naturalisieren, da sie Hierarchiesätze verwenden.

Die Beweise für permanente nicht einheitliche $TC^0$ verwenden Hierarchiesätze und scheinen nicht für ungleichmäßige Fälle zu funktionieren und scheinen sich nicht zu naturalisieren. Andererseits weiß ich nicht, ob sie relativieren, vielleicht mit einem passenden Begriff von Relativierung.

Kaveh
quelle

7

Interaktive Beweise relativieren nicht. Ich glaube nicht, dass sie sich einbürgern, da sie einheitlich sind.

Suresh Venkat
quelle

Beweise, Barrieren und P vs NP

Antworten: