Argumente für / gegen Kolmogorovs Vermutung über die Schaltungskomplexität von P

19

Nach (unbestätigter) historischer Darstellung hat Kolmogorov angenommen, dass jede Sprache in P eine lineare Schaltungskomplexität hat. (Siehe die frühere Frage Kolmogorovs Vermutung, dass P lineare Schaltkreise hat .) Beachten Sie, dass dies impliziert PNP.

Kolmogorovs Vermutung dürfte jedoch scheitern. Zum Beispiel schreibt Ryan Williams in einem kürzlich erschienenen Artikel: "Die Vermutung wäre überraschend, wenn sie wahr wäre. Für Sprachen in P die n100100 Zeit benötigen , erscheint es unwahrscheinlich, dass die Komplexität solcher Probleme auf magische Weise auf O(n) Größe schrumpfen würde. nur weil für jede Eingangslänge eine andere Schaltung entworfen werden kann. "

Andererseits ist Andrey Kolmogorov (1903-1987) weithin als einer der führenden Mathematiker des 20. Jahrhunderts anerkannt. Es ist kaum vorstellbar, dass er eine völlig absurde Vermutung aufgestellt hätte. Um es besser zu verstehen, habe ich versucht, einige Argumente zu finden, die seine überraschende Vermutung stützen könnten. Folgendes könnte ich mir ausdenken:

PSIZE(lin)LPL

  1. Es gibt einen bekannten expliziten Algorithmus (Turing-Maschine), der akzeptiert . Daraus können wir eine explizite Funktionsfamilie konstruieren, die eine superlineare Schaltungskomplexität haben muss. Dies kann jedoch als unwahrscheinlich angesehen werden, da niemand in mehr als 60 Jahren intensiver Forschung an Schaltkreisen ein solches Beispiel finden konnte.L

  2. Es ist kein expliziter Algorithmus für . Zum Beispiel wird seine Existenz mit nicht konstruktiven Mitteln wie dem Axiom of Choice bewiesen. Oder selbst wenn der explizite Algorithmus existiert, konnte ihn niemand finden. Angesichts der Tatsache, dass es unendlich viele Sprachen gibt, die die Rolle von , ist es unwahrscheinlich, dass sie sich alle so unfreundlich verhalten.LL

Wenn wir jedoch beide Optionen als unwahrscheinlich abtun, besteht die einzige verbleibende Möglichkeit darin, dass ein solches nicht existiert. Das bedeutet , was genau Kolmogorovs Vermutung ist.LPSIZE(lin)

Frage: Können Sie sich weitere Argumente für / gegen Kolmogorovs Vermutung vorstellen?

Andras Farago
quelle
2
Ich frage mich: Haben wir Kandidaten , um Kolmogorovs Vermutung zu widerlegen? Natürlich kann man jedes Problem in Betracht ziehen, das nachweislich eine superlineare Komplexität aufweist. Vielleicht haben einige von ihnen eher keine linearen Schaltkreise?
Bruno
2
Seien wir ehrlich, niemand hat die geringste Ahnung. (Bezüglich Goldman-Zitat auf Hollywood: "Niemand weiß etwas.") Die (unveröffentlichte) Vermutung ist vielleicht noch länger offen als P =? NP. Eine grobe Idee / ein ungefährer Blickwinkel, den es zu untersuchen gilt: Kompressionstheorie und Komprimierbarkeit. Dies ist im Grunde das, worauf Williams anspielt und was möglicherweise das Herzstück vieler Trennungen von Komplexitätsklassen sein könnte. Die Idee ist, dass es grundlegende Methoden / Algorithmen zum Codieren von Daten gibt und einige Muster per se schwieriger zu komprimieren sind, wenn (beliebige) Codierungen verwendet werden. Aber es scheint auch in diesem Bereich nur sehr wenige Ergebnisse zu geben.
vzn
1
Übrigens könnten die vielen Verbindungen zwischen Kolmogorov-Komplexität und rechnerischer Komplexität, die beispielsweise von Fortnow untersucht wurden, einen erklärenden Zusammenhang dazu haben, warum die Fragen so schwer zu lösen sind, weil so viele mit Kolmogorov-Komplexität zusammenhängende Fragen unentscheidbar sind ...?
vzn
1
@Bruno: Ich würde vermuten, dass -vollständige Probleme gute Kandidaten wären, z. B. lineare Programmierung oder das Schaltungswertproblem. Wenn dann können diese Probleme nicht einmal ungleichmäßig in Tiefe gelöst werden, so dass es zumindest vernünftig erscheint, zu raten, dass solche Probleme nicht auftreten sollten Auch in linearer Größe (und uneingeschränkter Tiefe) lösbar. Die Determinante könnte ein anderer vernünftiger Kandidat sein. Aber das sind nur Vorschläge - ich habe keine starken Gründe zu glauben, dass sie eine superlineare Schaltkreisgröße haben. PPNC
Joshua Grochow

Antworten:

22

Die Fußnote meines Beitrags, den Sie zitieren, bezieht sich zumindest auch auf ein heuristisches "Argument", das wir für Kolmogorovs Intuition halten - die positive Lösung von Hilberts dreizehntem Problem.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

Insbesondere wurde von Kolmogorov und Arnold bewiesen, dass jede stetige Funktion auf Variablen als eine Zusammensetzung von "einfachen" Funktionen ausgedrückt werden kann : Addition von zwei Variablen und stetige Funktionen auf einer Variablen. Daher hat über die "Basis" von einvariablen stetigen Funktionen und einer Addition von zwei Variablen jede stetige Funktion auf Variablen eine "Schaltungskomplexität" .nO(n2)nO(n2)

Es scheint, dass Kolmogorov glaubte, es gäbe ein diskretes Analogon, bei dem "stetig in Variablen" zu "boolesch in Variablen und poly -Zeit berechenbar" wird und bei dem die oben angegebene "Basis" zu zwei variablen booleschen Funktionen wird.nn(n)

Ryan Williams
quelle
Es wäre sehr interessant, wenn das diskrete Analogon, an das Kolmogorov glaubte, tatsächlich existieren würde. Vermutlich haben Forscher versucht, es zu finden, da es bis zu einem Beweis von . Was war die größte Straßensperre, auf die sie gestoßen sind? PNP
Andras Farago
3
Straßensperren? Ich glaube nicht , dass jemand den Weg gefunden hat :) Da die meisten Menschen glauben , dass nicht Größe Schaltungen, für jeden festen , wohl nur wenige Menschen haben sogar für die Straße sehen. PO(nk)k
Ryan Williams
11

Die Antwort von Stasys auf die vorherige Frage bietet eine mögliche Unterstützung: /cstheory//a/22048/8243 . Ich werde versuchen, es hier noch einmal zu wiederholen, so wie ich es verstehe. Die Schlüsselintuition besteht darin, eine Schaltung nicht als Algorithmus, sondern als Codierung einer Menge (der Menge, die sie akzeptiert) anzusehen. Wir können eine Obergrenze für die Codierungsgröße durch die Laufzeit des Algorithmus ermitteln ( dh eine Zeit TM in eine Größen- Schaltung umwandeln ), aber es ist nicht klar, welche umgekehrte Beziehung bestehen sollte. Befindet sich eine Sprache in , bedeutet dies möglicherweise, dass die Mitgliedschaft "lokal" genug ist, um sehr präzise codiert zu werden.ttP

Das heißt, die Zugehörigkeit zu ist eine Aussage über die Laufzeit eines Algorithmus, wohingegen lineare Schaltungen (möglicherweise) eine Aussage über die Codierungsgröße von Sätzen von Wörtern fester Länge sind. Beides sind Aussagen über die Einfachheit der Sprache, aber sie leben in vielleicht ganz unterschiedlichen Welten.P

Eine weitere Intuition Stasys erwähnt stammt aus dem „-Anzeige string“ einer Sprache, die ließen sich als unendliche Zeichenfolge formalisieren wobei Bit ist , wenn die - te lexicographic String in der Sprache und ist sonst. Ein (polytime) TM für die Sprache ist ein (schnelles) Orakel für den String - wenn binär angegeben wird, wird das te Bit erzeugt. Ein (linearer) Schaltkreis für Eingänge der Länge ist ein (prägnantes) Orakel für das Präfix der Länge des Strings. Die Vermutung wird "jede unendliche Zeichenkette, die ein" schnelles "Orakel hat, hat" prägnante "Präfix-Orakel."j1j0jjn2n

Keine der obigen erklärt, warum und "linear" die richtigen Parameter für die Anweisung sind, aber ich denke, sie zeigen, dass es eine natürliche Intuition gibt - dass Schaltungen wie Algorithmen und kompliziertere Algorithmen dies erfordern ähnlich komplizierte Schaltungen - könnten irreführend sein.P"

usul
quelle