Überraschende Ergebnisse bei der Komplexität (nicht auf der Liste der Komplexitätsblogs)

35

Was waren die überraschendsten Ergebnisse bei der Komplexität?

Ich denke, es wäre nützlich, eine Liste von unerwarteten / überraschenden Ergebnissen zu haben. Dies schließt sowohl überraschende als auch unerwartete Ergebnisse ein, als auch Ergebnisse, die anders ausfielen als erwartet.

Bearbeiten : Angesichts der Liste von Gasarch, Lewis und Ladner auf dem Komplexitätsblog (darauf hingewiesen von @Zeyu) wollen wir uns in diesem Community-Wiki auf Ergebnisse konzentrieren, die nicht in der Liste enthalten sind. Vielleicht führt dies nach 2005 zu einer Fokussierung auf die Ergebnisse (gemäß dem Vorschlag von @ Jukka).

Ein Beispiel: Schwaches Lernen = starkes Lernen [Schapire 1990] : (Überraschenderweise?) Wenn Sie einen Vorteil gegenüber dem zufälligen Erraten haben, erhalten Sie PAC-Lernen. Führen Sie zum AdaBoost-Algorithmus.

Lev Reyzin
quelle
Mir ist klar, dass dies möglicherweise außerhalb des Anwendungsbereichs liegt, aber es ist gut, die Grenzen in der Beta zu überprüfen, oder? :)
Lev Reyzin
2
Sicherlich zum Thema, würde ich sagen.
Jukka Suomela

Antworten:

29

Hier ist der Gastbeitrag von Bill Gasarch mit Hilfe von Harry Lewis und Richard Ladner: http://blog.computationalcomplexity.org/2005/12/surprising-results.html

Zeyu
quelle
wow das habe ich irgendwie verpasst! Wahrscheinlich brauchen wir dann keine Liste zu machen :)
Lev Reyzin
2
Vielleicht wäre es gut, sich hier auf überraschende Ergebnisse seit 2005 zu konzentrieren.
Jukka Suomela
21

Wenn PNP , dann gibt es einen "Diagonalisierungs" Beweis dafür.

Dieses Ergebnis ist Kozen zu verdanken. Nicht jeder stimmt dem zu, was er als "Diagonalisierungsbeweis" bezeichnet.

Kaveh
quelle
1
Dies war für mich sehr überwachend, da ich oft gehört hatte, dass Diagonalisierung von P trennen kann . NPP
Kaveh
1
Können Sie eine Referenz geben? Ich habe noch nie von diesem Ergebnis gehört, aber es klingt sehr interessant. Zumal es im krassen Gegensatz zu meiner Intuition steht, dass die Relativierung das ausschließt, was ich allgemein als Diagonalisierungsbeweise betrachte ...
Joshua Grochow
3
D. Kozen, "Indexing of subrecursive classes", 1978
Kaveh
In welcher Beziehung steht dies zum Ergebnis von Baker Gill Solovay 1975?
VZN
14

NL

Kaveh
quelle
12

Ich würde sagen, die jüngste Arbeit von Jain, Upadhyay und Watrous zeigt, dass QIP = IP = PSPACE ziemlich überraschend ist. Meiner Meinung nach ist QIP = IP weniger interessant als vielmehr die Tatsache, dass das gesamte QIP in einem interaktiven 3-Runden-Quanten-Proof simuliert werden kann. Eine ziemlich coole Demonstration der Kraft der Quantenparallelität.

Was mich immer wieder überrascht, ist, dass BPP wahrscheinlich P ist. Es wirft viele philosophische Fragen in Bezug auf die Natur der Zufälligkeit auf.

Henry Yuen
quelle
3
QIP = QIP (3) ist seit ungefähr 10 Jahren bekannt. Das QIP = PSPACE-Papier zeigte das nicht.
Robin Kothari
Das aktuelle Ergebnis QIP = PSPACE stammt von Jain, Ji, Upadhyay und Watrous.
Tsuyoshi Ito
10

Theorem der Razborov-Rudich Natural Proofs.

(AFAIK) Die Leute waren sehr zuversichtlich, die unteren Grenzen der Schaltung zu beweisen, aber nach diesem Satz hörten viele auf zu arbeiten und gingen zu anderen Themen über.

Kaveh
quelle
10

Die Zählversion des Monotone-SAT-Problems ist # P-complete.

FF

Dieses Ergebnis hat mich sehr überrascht, da die Entscheidungsversion des Monotone-SAT-Problems trivial ist.

Es ist allgemein bekannt, dass es in P Entscheidungsprobleme gibt, deren Zählversionen # P-vollständig sind (ein Beispiel ist 2-SAT). Aber dieser Fall ist meiner Meinung nach ein bisschen "anders": Das Finden einer zufriedenstellenden Zuordnung einer Monotone-SAT-Instanz ist nicht nur einfach (wie zum Beispiel das Finden einer zufriedenstellenden Zuordnung einer 2-SAT-Instanz), sondern auch dramatisch trivial. Nicht nur einfach: Trivialität im wahrsten Sinne des Wortes. Man beachte, dass beispielsweise bei einer 2-SAT-Instanz diese natürlich entweder zufriedenstellend oder nicht zufriedenstellend sein kann. Bei einer Monotone-SAT-Instanz, von der Sie bereits im Voraus wissen, dass sie durchaus zufriedenstellend ist: Sie kann auf keinen Fall unbefriedigend sein. Dies bestätigt, dass auch beide Probleme einfach sind und sich in ihrem Grad an "Entscheidungsfreiheit" unterscheiden. Auf der anderen Seite ist ihr Grad an "Zählunruhe" genau gleich.

Dieser starke Kontrast zwischen den folgenden Fakten

  1. Die Entscheidung für Monotone-SAT ist dumm und trivial
  2. Monotone-SAT zu zählen ist extrem schwierig

ist meiner Meinung nach zumindest faszinierend.

Giorgio Camerani
quelle