Schaltkreisuntergrenzen und kolmogorov Komplexität

21

Betrachten Sie die folgenden Überlegungen:

Sei die Kolmogorov-Komplexität der Zeichenkette x . Chaitins Unvollständigkeitssatz sagt das ausK(x)x

für jedes konsistentes und formales System ausreichend starkes gibt es eine Konstante T (nur abhängig von dem formalen System und seiner Sprache) , so dass für all Strings x , S nicht nachweisen kann , dass K ( x ) T .STxSK(x)T

Sei eine Boolesche Funktion für n Variablen, wenn die Kolmogorov-Komplexität ihres Spektrums höchstens k beträgt . Sei S ( f n ) die Schaltungskomplexität von f n , dh die Größe der minimalen Schaltungsberechnung von f n .fnnkS(fn)fnfn

A (grob) Obermaterial gebunden an ist S ( f n ) c B B ( k ) n für eine Konstante c und B B ( k ) ist eine Besetzt Beaver - Funktion (die maximal mögliche Schritte a Turingmaschine mit einer Beschreibung der Größe k ausführen kann). ( Konstruieren Sie für jede 1 im Spektrum den Minterm der entsprechenden Wahrheitszuweisung und nehmen Sie OR aller dieser Minterms zusammen.)S(fn)

S(fn)cBB(k)n
cBB(k)k1

Angenommen , wir haben für eine unendliche Familie von Booleschen Funktionen einen formalen Beweis, dass L Schaltkreise mit superlinearer Größe erfordert, d. HL={fn}nL

, wobei g ( n ) & ohgr; ( 1 ) .

Snn0, g(n)nS(fn)
g(n)ω(1)

Wenn wir als ausreichend groß, haben wir g ( n ) > c B B ( T )n

g(n)>cBB(T)

Dies wäre insbesondere ein Beweis dafür, dass die Kolmogorov-Komplexität des Spektrums von mindestens T ist , was unmöglich ist.fnT

Dies führt zu zwei Fragen:

1) In der obigen Argumentation sollte etwas falsch sein. Hauptsächlich, weil es die unteren Schranken der superlinearen Schaltung formal nicht nachweisbar machen würde.

2) Kennen Sie ähnliche Ansätze, um Barrieren für Untergrenzen aufzuzeigen, dh zu zeigen, dass bestimmte Arten von (Schaltungs-) Untergrenzen formal nicht beweisbar sind?

Magnus Find
quelle
interessante Ideen. etwas verwandt mit dem razborov / rudich Beweis für "natürliche Beweise", die Barrieren für P =? NP skizzieren (aber wahrscheinlich auch anwendbar auf andere Komplexitätsklassentrennungen, wie sie als Beispiele in der Arbeit aufgeführt sind). Haben Sie diese Arbeit gelesen? siehe auch Barrieren P = & Dgr; NP und Barrieren / monotone Schaltungskomplexität . Scheinbare Hinweise darauf, dass Komplexitätsklassentrennungen in ihrer Struktur Unprovabilitätsbeweisen ähneln.
vzn
2
Können Sie das "Spektrum" von f_n erläutern? Gibt es eine Möglichkeit, die Frage ohne Bezugnahme auf das "Spektrum" zu formulieren?
vzn
Es ist wahrscheinlich richtig, dass man die Komplexität von Funktionen untersuchen kann, indem man das kleinste TM [im Sinne von Zustandstabelle / Zuständen] untersucht, das sie berechnet, und dass dies in etwa den unteren Grenzen der Schaltung entspricht. Wenn Sie zeigen können, dass es nicht wirklich schwierig ist, das kleinste TM zu finden, haben Sie möglicherweise etwas dabei. Es ist jedoch "einfach", das kleinste TM durch kanonische Aufzählung von Schaltkreisen oder TMs zu finden. Wenn Sie sich überlegen, warum dieser Ansatz funktioniert, kann es hilfreich sein, zu verstehen, warum die Frage nicht zu einem Problem führt.
vzn
1
(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))

Antworten:

11

NfnTNN>g1(cBB(T))BB

domotorp
quelle
S
1

A(k)K(A(k))kkK(A(k))k

BB(T)

α(k)kα(k)K(0α(k)+1)>k

Yuval Filmus
quelle
Warum ist diese Situation problematisch? Sie haben kein Programm angegeben, dessen Ausgabe A (k) und dessen Länge kleiner als k wäre.
Domotorp
BB(k)k
Es ist (wohl) in demselben Sinne problematisch wie die ursprüngliche Frage.
Yuval Filmus
Ich verstehe es immer noch nicht. Sie zeigen keine Schnur und keinen Beweis dafür, dass die Komplexität von Kolmogorov groß ist. Sie legen einen Beweis dafür vor, dass es eine Zeichenfolge gibt, deren Komplexität groß ist.
Sasho Nikolov
Ich denke, dass sie auf unterschiedliche Weise problematisch sind. Während ich es lese, verweisen Sie auf eine bestimmte wahre Aussage, für die es keinen Beweis gibt. Wie ich in meiner Frage dargelegt habe, geht es um einen Beweis für etwas, das nicht beweisbar ist.
Magnus Find