Kolmogorovs Vermutung, dass lineare Schaltkreise hat

28

In seinem Buch Boolean Function Complexity erwähnt Stasys Jukna (Seite 564), dass Kolmogorov glaubte, dass jede Sprache in P Schaltkreise linearer Größe hat. Es wird keine Referenz erwähnt und ich konnte nichts online finden. Weiß jemand mehr darüber?

Hamid
quelle
4
Paging @Stasys :)
Suresh Venkat
19
Diese "Vermutung" von Kolmogorov ist nur ein Gerücht. Es wurde natürlich nirgendwo veröffentlicht oder so. In der ehemaligen UdSSR bedeutete "Veröffentlichen" von Mathematik etwas anderes: Reden Sie in einem Seminar oder erzählen Sie es Ihren Kollegen beim Mittagessen. Das Zählen von Papieren war kein Thema. Ich kann also nicht ausschließen, dass diese "Vermutung" Levin gerade von Kolmogorov während seines Spaziergangs zu einem Seminar an der MGU (Moskauer Universität) erzählt wurde. (Eigentlich habe ich auch diese Art zu rechnen empfohlen.) Also nimm das nicht zu ernst - nur als "Gerücht", das (unnötig zu sagen) im Laufe der Jahre nicht widerlegt wurde ...
Stasys
5
@vzn für jedes feste weil . Letzteres wird durch Theorem zu gestärkt . k k N : Σ P 4s i z e ( n k ) Σ P 2Psize(nk)PNPkkN:Σ4Psize(nk)Σ2P
Sasho Nikolov
2
@Stasys, du solltest das als Antwort posten, damit die Frage beantwortet wird (damit die Site sie nicht immer auf die Titelseite schiebt).
Kaveh

Antworten:

24

[Aufgrund eines Vorschlags von Kaveh stelle ich meinen (etwas erweiterten) Kommentar als Antwort zur Verfügung]

Diese "Vermutung" von Kolmogorov ist nur ein Gerücht. Es wurde nirgendwo veröffentlicht. In der ehemaligen UdSSR bedeutete "Veröffentlichen" von Mathematik etwas anderes als das, was es heute tut: einen Vortrag auf einem Seminar halten oder Ihren Kollegen beim Mittagessen davon erzählen. Das Zählen von Papieren war kein Thema. (Eigentlich habe ich auch diese Art zu rechnen empfohlen.) Ich kann die Möglichkeit nicht ausschließen, dass diese "Vermutung" Levin gerade von Kolmogorov während seines Spaziergangs zu einem Seminar an der Moskauer Universität erzählt wurde. Nehmen Sie das also nicht zu ernst als formelle Vermutung; Es ist nur ein Gerücht, dass (natürlich) im Laufe der Jahre nicht widerlegt wurde. Aber da ein Riese wie Kolmogorov ernsthaft über dieses Problem nachdachte und die Möglichkeit einer "Teufelsmacht" nicht ausschloss, sollte die Vermutung ernsthaft genug behandelt werden.

Hier ist eine (sehr, sehr grobe) Spekulation meines Verständnisses dieser Vermutung. Unsere (anscheinend falsche) Vorstellung von der Funktionsweise von Schaltkreisen beruht darauf, dass die Berechnung von einem Programm als sequentieller Prozess betrachtet wird, der nach und nach Informationen über die Eingabezeichenfolge sammelt. Diese Intuition stammt aus unserer Sicht der Funktionsweise einer Turing-Maschine. Jede Eingabezeichenfolge bestimmt jedoch eine Teilschaltung (wobei oder ). Und damit eine Schaltung korrekt ist, ist es ausreichend, dass die Mengen von Teilschaltungen für und disjunkt sind. Das heißt, eine Schaltung ist eine kompakte "lokale Codierung" einer gegebenen Partition vonf ( x ) = 1 f ( x ) = 0 f - 1 ( 1 ) f - 1 ( 0 ) n f n 2 n f n f n c c N cxf(x)=1f(x)=0f1(1)f1(0)n-Würfel. Die Länge dieses Codes ist die Kolmogorov-Komplexität der gegebenen binären Zeichenkette der Länge . Ein polynomieller Zeitalgorithmus leistet jedoch mehr: Er gibt eine "globale Codierung" der gesamten unendlichen Zeichenfolge für alle . Nun muss eine unendliche Zeichenkette die eine Codierung der Größe zulässt, "einfach" sein, und ihre Präfixe "sollten" noch kompaktere "lokale" Codierungen zulassen. Natürlich bleibt es ein Rätsel, warum Kolmogorov dachte, dass dann "lokale" Codierungen sogar von der Größe für einige ausreichen könnten ...fn2nfnfnccnc

PS: Entschuldigung, vergessen hinzuzufügen: Eine hervorragende Bestätigung meiner "These", dass Schaltkreise als (statische) Codes und nicht als (dynamische) Algorithmen angesehen werden sollten, ist der berühmte Satz von David Barrington, dass die gesamte Klasse durch Polynom simuliert werden kann -size Verzweigungsprogramme der Breite 5. Die Ansicht "Informationen sammeln" ist hier völlig falsch: Es ist nicht einmal klar, wie die Mehrheitsfunktion berechnet werden kann, wenn nur 5 Bits an Informationen gespeichert werden. Eine clevere Idee von David war nur zu verschlüsselnNC1das Verhalten einer bestimmten Formel durch bestimmte Sequenzen von 5-Permutationen und um zu zeigen, dass akzeptierte und abgelehnte Zeichenfolgen unterschiedliche Codes erhalten. Der Punkt ist, dass ein Verzweigungsprogramm auch nicht "berechnet" --- es codiert eher Eingabezeichenfolgen durch seine Unterprogramme: Wenn eine Eingabe eintrifft, verschwinden inkonsistente Kanten, und wir haben einen Code für diese Eingabe.

Stasys
quelle
Gibt es nicht triviale Beispiele für Sprachen, die diese Vermutung stützen?
Igor Shinkar
@Igor: Ich weiß es nicht. Einige (schwache) Indikationen werden hier erwähnt . Eigentlich neige ich zur Antwort von GMB: Die Vermutung wurde höchstwahrscheinlich durch die Lösung des 13. Hilbert-Problems angeregt, nicht durch kombinatorische Überlegungen.
Stasys
8

Ich kenne mich mit diesem Thema bei weitem nicht so gut aus wie Stasys, aber ich habe eine andere Rechtfertigung für diese Vermutung gehört, die ich genauso gut teilen könnte.

Ich hörte, dass die Vermutung auf der positiven Lösung von Hilberts dreizehntem Problem beruhte, die von Komolgorov und seinem Schüler Arnold gemeinsam gelöst wurde. Der Satz (der viel allgemeiner ist als Hilberts erklärtes Problem) besagt:

Jede stetige Funktion einer endlichen Anzahl von Variablen kann als endliche Zusammensetzung von Funktionen mit einer Variablen sowie als endliche Anzahl von Anwendungen des binären Operators ausgedrückt werden .+

Mir wurde gesagt, dass dies auf der Grundlage einiger Implementierungsdetails des Beweises dieses Theorems als kontinuierliches Analogon der Behauptung angesehen werden kann, dass .kPSIZE(nk)

Tut mir leid, dass ich nicht qualifiziert bin, genauer zu sein - wenn jemand diese Idee gehört hat, könnte er mir vielleicht helfen.

GMB
quelle
Können Sie einen Schiedsrichter für das geben
?
@ GMB: gut beobachtet - dies könnte eine noch genauere Erklärung für den Grund sein, diese Vermutung aufzustellen.
Stasys