Nachrufe auf tote Vermutungen

44

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 XP S P A C E X XIP=PSPACEIPXPSPACEXX

  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 PPBPPP=BPP

Welche anderen Vermutungen haben den Test der Zeit nicht bestanden?

Andras Farago
quelle
3
Vor IP = PSPACE wurde es sogar für möglich gehalten, dass , siehe Fortnow-Sipser 1988 . Ich weiß nicht, ob dies als separate Antwort mit derselben Auflösung gilt oder ob es Ihrem Beispiel 1 zu ähnlich ist.coNPIP
Joshua Grochow,
4
Das Programm von Hilbert ("... die Grundfragen der Mathematik ein für allemal beseitigen ...") und seine "Vermutung" über die Entscheidbarkeit formaler Theorien [~ 1920], das "abstürzte" (ziemlich schnell [1931]) ]) in Godels Unvollständigkeitssatz :-)
Marzio De Biasi
2
Die Rezension dieses Papiers von Kreisel lautet: "Dieses Papier stellt fest, dass jede rekursiv aufzählbare (Neu-) Menge in Bezug auf Exponentiation existenziell definiert werden kann. ... Diese Ergebnisse stehen oberflächlich im Zusammenhang mit Hilberts zehntem Problem in Bezug auf (gewöhnliche, dh nicht exponentielle) ) Diophantingleichungen ... Es ist nicht ganz plausibel, dass alle (gewöhnlichen) Diophantinprobleme einheitlich auf eine feste Anzahl von Variablen mit festem Grad reduzierbar sind, was der Fall wäre, wenn alle Neueinstellungen Diophantin wären. " (Siehe auch hier .)
Andrés E. Caicedo
3
Auch der Post Surprising Results from Computational Complexity-Blog.
Kaveh

Antworten:

22

NLcoNL . 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.NPcoNP

Joshua Grochow
quelle
'Analogie'? eins ist zeit und ein anderes ist raum nein?
7
@Arul: Ja. Das ist eine Analogie zwischen Komplexitätsklassen, die durch Zeitbegrenzung definiert sind, und Komplexitätsklassen, die durch Raumbegrenzung definiert sind ...
Joshua Grochow
Aber Zeit und Raum sind nicht gleich (zumindest mutmaßlich)
25
@Arul: Richtig. Genau deshalb ist es nur eine Analogie ...
Joshua Grochow
19

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.IP=PSPACEcoNPIP

Joshua Grochow
quelle
18

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 .

Paul Beame
quelle
17

Die -Konzeptur: Jeder deterministische Algorithmus für benötigt Zeit.3SUM3SUMΩ(n2)

Dies wurde 2014 von Allan Grønlund und Seth Pettie widerlegt, die einen deterministischen Algorithmus gaben, der in der Zeit läuft [1].O(n2/(logn/loglogn)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]

Mangara
quelle
5
Wie um alles in der Welt haben sie diesen Titel an den Rezensenten vorbei bekommen?
David Zhang
17

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.“

Andrés E. Caicedo
quelle
9

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.

Marzio De Biasi
quelle
7

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/2PCP1,s[logn,3]P

Tatsächlich zeigt SDP , was die Komplexität solcher PCPs stark einschränkt.PCP1,1/2[logn,3]=P

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

Joe Bebel
quelle
1

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.

vzn
quelle
1
Welche Vermutung markieren Sie? Außerdem scheint die Komplexität der Schaltung sowohl sehr aktiv als auch recht erfolgreich zu sein, zum Beispiel Rossmans mehrfacher Durchbruch. Weitere Informationen finden Sie in Juknas maßgeblichem Lehrbuch.
András Salamon
Es gibt mehrere miteinander zusammenhängende Ideen, aber zB die "grobe" Vermutung, dass Schaltkreise im Allgemeinen oder eine spezielle Form (zB monoton) P gegen NP oder starke Untergrenzen beweisen könnten ... es war nie genau formalisiert, sondern zirkuliert in vielen (alten) schaltungstheoretische Arbeiten. es wird auch nicht strikt widerlegt, sondern im nachhinein bis 2020 stark überarbeitet. Insbesondere die monotone Circuit Story ist eine "Beinahe-Umkehr".
vzn 06.10.15 Uhr
8
Wenn Sie einige spezifische Referenzen als Unterstützung für eine monotone Schaltkreisumkehr zitieren, dann wäre das eine schöne Antwort. Aber das oben Genannte wirkt, als würde man viele Worte an die Wand werfen und auf etwas Stock hoffen. Es hat Nuancen, aber es fehlt eine klare These. In meiner Lektüre habe ich nicht den Eindruck erweckt, dass monotone Schaltkreise jemals für besonders leistungsfähig gehalten wurden.
András Salamon
@ AndrásSalamon: Ich denke, diese Sichtweise ist im Nachhinein von Vorteil. Das heißt, nach Razborovs exponentieller Untergrenze für monotone Schaltkreise für Cliquen herrschte meiner Meinung nach allgemeiner Optimismus, dass viel größere Schaltkreisuntergrenzen (wie ) "gleich um die Ecke" lagen. (Vielleicht nicht so verbreitet wie der Glaube, dass , aber ich denke, weit genug verbreitet, um als Antwort auf diese Frage erwähnt zu werden.)P n e q N PNPP/polyPneqNP
Joshua Grochow
@ JoshuaGrochow, ich stimme zu, aber das ist ganz anders als der verwirrte Thread oben. Vielleicht eine Antwort wert?
András Salamon