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.
quelle
Antworten:
Hier ist der Gastbeitrag von Bill Gasarch mit Hilfe von Harry Lewis und Richard Ladner: http://blog.computationalcomplexity.org/2005/12/surprising-results.html
quelle
WennP≠ NP , dann gibt es einen "Diagonalisierungs" Beweis dafür.
Dieses Ergebnis ist Kozen zu verdanken. Nicht jeder stimmt dem zu, was er als "Diagonalisierungsbeweis" bezeichnet.
quelle
Bei Barriers I stimmte ein Gremium führender Komplexitätstheoretiker zu, dass Barringtons Theorem das Ergebnis war, das sie am meisten überraschte. Fortnow erklärt Barringtons Satz hier: http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html
quelle
quelle
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.
quelle
Gödels Unvollständigkeitssätze
quelle
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.
quelle
Die Zählversion des Monotone-SAT-Problems ist # P-complete.
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
ist meiner Meinung nach zumindest faszinierend.
quelle
Dass die Axiome der Wahl und der Entschlossenheit nicht kompatibel sind.
quelle