Nachrufe auf tote Vermutungen

Ich suche nach Vermutungen über Algorithmen und Komplexität, die von vielen zu einem bestimmten Zeitpunkt als glaubwürdig angesehen wurden, aber später aufgrund zunehmender Gegenbeweise entweder widerlegt oder zumindest nicht geglaubt wurden. Hier sind zwei Beispiele:

1. Zufällige Orakelhypothese: Beziehungen zwischen Komplexitätsklassen, die für fast alle relativierten Welten gelten, gelten auch für den nicht relativen Fall. Dies wurde durch das Ergebnis widerlegt , und indem gezeigt wurde, dass für fast alle zufälligen Orakel , siehe The Random Oracle Hypothesis is False .I P X ≠ P S P A C E X$IP=PSPACE$$IP^X\neq PSPACE^X$$X$

2. Die Zufälligkeit begrenzter Fehler erweitert die Potenz der Polynomzeit (dh ) ordnungsgemäß . Dies wurde eine Weile geglaubt, aber später hat sich aufgrund ausgefeilter Ergebnisse der Derandomisierung und ihrer Verbindungen zur Schaltungskomplexität die entgegengesetzte Vermutung ( ) durchgesetzt (obwohl immer noch offen).P = B P $P\neq BPP$$P=BPP$

Welche anderen Vermutungen haben den Test der Zeit nicht bestanden?

$\mathsf{NL} \neq \mathsf{coNL}$ . Vor dem Ergebnis, dass diese beiden gleich waren, wurde allgemein angenommen, dass sie sich in Analogie zu der Annahme unterscheiden, dass (dh das allgemeine Prinzip, dass "Nichtdeterminismus Nichtdeterminismus ist anders "; dies stellte sich unter räumlichen Komplexitätsgrenzen, die zumindest logarithmisch waren, als falsch heraus.$\mathsf{NP} \neq \mathsf{coNP}$

Vor wurde es für möglich gehalten, dass sogar nicht in : In Fortnow-Sipser 1988 vermuteten sie, dass dies der Fall ist, und gaben an ein Orakel relativ zu dem es wahr war.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{coNP}$$\mathsf{IP}$

Verzweigungsprogramme mit konstanter Breite erfordern mehr als eine Polynomlänge : Nachdem Furst-Saxe-Sipser und Ajtai 1981 gezeigt hatten, dass AC ^0- Schaltkreise nicht zählen können, schien es ein logischer nächster Schritt zu sein, zu zeigen, dass Verzweigungsprogramme mit konstanter Breite Polynomlänge sind Länge konnte nicht zählen, was weithin vermutet wurde, um zu halten. David Barrington hat 1986 gezeigt, dass sie nicht nur zählen können, sondern auch NC ^{1 entsprechen} .

Die -Konzeptur: Jeder deterministische Algorithmus für benötigt Zeit.$\mathsf{3SUM}$$\mathsf{3SUM}$$\Omega(n^2)$

Dies wurde 2014 von Allan Grønlund und Seth Pettie widerlegt, die einen deterministischen Algorithmus gaben, der in der Zeit läuft [1].$O(n^2/(\log n/\log \log n)^{2/3})$

[1] Dreier, Entartete und Liebesdreiecke. Allan Grønlund und Seth Pettie. In Foundations of Computer Science (FOCS) 2014, S. 621-630. arXiv: 1404.0799 [cs.DS]

Die Lösung von Hilberts zehntem Problem durch Davis, Matiyasevich, Putnam und Robinson zeigt, dass die rekursiv aufzählbaren Mengen genau die diophantinischen Mengen sind.

(Ich reproduziere hier einen Blogeintrag , Hindsight , von vor ein paar Jahren, wie in den Kommentaren vorgeschlagen.)

Aus Georg Kreisels Übersichtsartikel über das Entscheidungsproblem für exponentielle diophantische Gleichungen von Martin Davis, Hilary Putnam, und Julia Robinson, Ann. von Mathe. (2), 74 (3) , (1961), 425–436. MR0133227 (24 # A3061) .

In diesem Artikel wird festgestellt, dass jede rekursiv aufzählbare (Neu-) Menge in Bezug auf die Potenzierung existenziell definiert werden kann. […] Diese Ergebnisse hängen oberflächlich mit Hilberts zehntem Problem mit (gewöhnlichen, dh nicht exponentiellen) diophantinischen Gleichungen zusammen. Obwohl der Beweis der Ergebnisse der Autoren sehr elegant ist, werden weder in der Theorie der Zahlen noch in der Theorie der Zurücksetzungen rekonditionierte Tatsachen verwendet, so dass es wahrscheinlich ist, dass das vorliegende Ergebnis nicht eng mit Hilberts zehntem Problem zusammenhängt. Es ist auch nicht ganz plausibel, dass alle (gewöhnlichen) diophantinischen Probleme einheitlich auf eine feste Anzahl von Variablen mit festem Grad reduziert werden können, was der Fall wäre, wenn alle Neueinstellungen diophantinisch wären.

Natürlich ist mein Lieblingszitat in Bezug auf das zehnte Problem das Vorwort von Martin Davis zu Yuri Matiyasevichs Hilberts zehntem Problem .

In den sechziger Jahren hatte ich oft Gelegenheit, über Hilberts Zehntes Problem zu referieren. Zu dieser Zeit war bekannt, dass die Unlösbarkeit aus der Existenz einer einzigen diophantinischen Gleichung resultieren würde, die eine von Julia Robinson formulierte Bedingung erfüllte. Es schien jedoch außerordentlich schwierig, eine solche Gleichung zu erstellen, und tatsächlich war die vorherrschende Meinung, dass es wahrscheinlich keine solche geben würde. In meinen Vorlesungen möchte ich die wichtigen Konsequenzen hervorheben, die sich aus einem Beweis oder einer Ablehnung der Existenz einer solchen Gleichung ergeben würden. Zwangsläufig wurde ich während der Fragestunde nach meiner eigenen Meinung gefragt, wie sich die Dinge entwickeln würden, und ich hatte meine Antwort parat: „Ich denke, dass die Hypothese von Julia Robinson wahr ist und dass sie von einem klugen jungen Russen bewiesen wird.“

Das Hilbert-Programm und seine "Vermutung" über die Entscheidbarkeit formaler Theorien. Es wurde in den frühen 1920er Jahren formuliert und von ihm und seinen Mitarbeitern an der Universität Göttingen und anderswo in den 1920er und 1930er Jahren verfolgt.

"Mit dieser Neugründung der Mathematik - die man zutreffend als Beweistheorie bezeichnen kann - glaube ich, die Grundfragen der Mathematik ein für allemal zu klären, indem man jede mathematische Aussage in eine konkret ausstellbare und rigoros ableitbare Formel umwandelt und damit die ganze Fragenkomplex in den Bereich der reinen Mathematik. "

Es ist bekannt, dass Hilberts Vorschläge (ziemlich schnell [1931]) in Godels Unvollständigkeitssatz "zusammenstießen" .

Für einen schönen Überblick über das Hilbert-Programm und spätere Entwicklungen siehe: Richard Zach; Hilberts Programm damals und heute; Handbuch der Wissenschaftstheorie. Band 5: Philosophie der Logik; 2006

Siehe auch die Antwort von Andrés Caicedo für einen anderen Aspekt der Geschichte: das zehnte Hilbert-Problem, das erst 1970 gelöst wurde.

In einem Vortrag von Madhu Sudan * behauptete er, es gebe einen Glauben, dass es gäbe, so dass über semidefinite Programmierung vor dem Beweis von Håstads Drei-Bit-PCP-Theorem.$s > 1/2$$\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$

Tatsächlich zeigt SDP , was die Komplexität solcher PCPs stark einschränkt.$\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$

(* Ich fand diesen Vortrag von Madhu in "Computational Complexity Theory, herausgegeben von Rudich / Wigderson")

Die Vermutungen reichen von formal bis informell. Zum Beispiel wurde Hilberts berühmte Vermutung über die Entscheidbarkeit der Mathematik in ein paar Probleme formalisiert, z. B. Hilberts 10. Problem, aber es war auch eine grandiose informelle Vermutung, die sich über das gesamte Gebiet erstreckte. es kann auch als vorgeschlagenes Forschungsprogramm angesehen werden.

Ein einfaches Rezept, um einen solchen "Nachruf auf tote Vermutungen" zu finden, wäre, die "Meta-" Aussage "[x] Vermutung könnte in meinem Leben bewiesen werden" in Betracht zu ziehen. Die Mathematikliteratur steckt voller solcher Aussagen / Erwartungen, die sich als "falsch" herausstellten, im Sinne einer völligen Widerlegung der Erwartungen hinsichtlich Schwierigkeit und Zugänglichkeit eines Beweises. Ein Klassiker ist die Riemannsche Vermutung, die seit über 1 ½ Jahrhunderten offen ist. Dasselbe Modell auf die Komplexitätstheorie anzuwenden ist nicht so einfach, da die Komplexitätstheorie ein viel jüngeres wissenschaftliches Gebiet ist. Hier ist jedoch ein Schlüsselbeispiel.

Die frühe Entdeckung des P-gegen-NP-Problems (nunmehr seit 4½ Jahrzehnten offen) hatte eine Art Unschuld dahingehend, dass die ursprünglichen Ermittler nicht ahnten und sich nicht vorstellen konnten, wie schwierig oder übergreifend sich das Problem herausstellen würde. Um dies genauer zu machen, betrachten wir das Gebiet der Schaltungskomplexität, das in den frühen 1980er Jahren zB von Sipser erfunden wurde. Dies war ein Forschungsprogramm, das Hilberts ähnelte und zum Teil dazu diente, P gegen NP anzugreifen. Einige der historischen Ergebnisse werden von Arvind in dieser Zusammenfassung / Einführung zusammengefasst. Die Computational Complexity Column, BEATCS 106 :

Die 1980er Jahre waren eine goldene Zeit für die unteren Grenzen der Booleschen Schaltungskomplexität. Es gab große Durchbrüche. Beispiel: Razborovs Exponentialgrößenuntergrenze für monotone Boolesche Schaltkreise, die die Clique-Funktion berechnen, und die Razborov-Smolensky-Superpolynomgrößenuntergrenze für Schaltkreise mit konstanter Tiefe mit MOD _p- Gattern für Primzahl p. Diese Ergebnisse machten die Forscher optimistisch für Fortschritte bei großen Fragen der unteren Schranken und bei der Trennung von Komplexitätsklassen. In den letzten zwei Jahrzehnten verwandelte sich dieser Optimismus jedoch allmählich in Verzweiflung. Wir wissen immer noch nicht, wie man superpolynomiale Untergrenzen für Schaltungen mit konstanter Tiefe mit MOD _6- Gattern für eine in Exponentialzeit berechenbare Funktion beweist .

Es gab zwei Schlüsselpapiere, die Hoffnungen auf dem Feld zerstörten. Razborov hatte großartige / gefeierte Ergebnisse in Bezug auf die Clique-Funktion, schrieb dann aber zwei gegensätzliche Artikel. Eine Veröffentlichung zeigte, dass Matching, ein P-Zeit-Problem, exponentielle monotone Schaltungen erfordert und daher in gewissem Sinne der monotone Schaltungsansatz für untere Grenzen vereitelt wurde, weil die Komplexität nicht mit nichtmonotonen ("vollständigen") Schaltungen übereinstimmt (immer noch nicht vollständig) verstanden).

Dies wurde in seiner berühmten Arbeit Natural Proofs coauthored with Rudich erweitert, in der gezeigt wird, dass alle früheren Circuit Lower Bound-Proofs einem bestimmten Muster unterliegen, das nachweislich eine Schwäche im Sinne eines Widerspruchs mit vermuteten Lower Bound-Werten von Hard-Random-Number-Generatoren aufweist Kryptographie.

Bis zu einem gewissen Grad sind die Schaltkreise "in Ungnade gefallen". es ist immer noch ein riesiges Forschungsgebiet, aber die konventionelle Weisheit, die durch technische Ergebnisse gestützt wird, ist, dass eine Art spezielles, noch unbekanntes Beweismuster / -struktur erforderlich wäre, um starke Ergebnisse in dem Gebiet zu erzielen, wenn dies überhaupt möglich ist. in der Tat könnte man in ähnlicher Weise vorschlagen, dass sogar "starke untere Schranken in der Komplexitätstheorie" insgesamt als äußerst schwierig angesehen werden, und dies wurde in den jüngeren Tagen des Feldes nicht allgemein erwartet / vorhergesagt. aber auf der anderen Seite ordnet dies sie dann dort in Schwierigkeit / Bedeutung / Wichtigkeit mit den großen (offenen) Problemen der Mathematik ein.