Kolmogorovs Vermutung, dass lineare Schaltkreise hat

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?

[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 $x$$f(x)=1$$f(x)=0$$f^{-1}(1)$$f^{-1}(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 ...$f_n$$2^n$$f$$n$$f$$n^c$$cn$$c$

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üsseln$NC^1$das 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.

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 .$\exists k \, \, \, P \subset SIZE(n^k)$

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