Schaltkreisuntergrenzen und kolmogorov Komplexität

Betrachten Sie die folgenden Überlegungen:

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

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

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

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

S (f_{n}) \leq c \cdot B B (k) \cdot n

$S(f_n)\leq c\cdot BB(k) \cdot n$

c

$c$

B B (k)

$BB(k)$

k

$k$

1

$1$

Angenommen , wir haben für eine unendliche Familie von Booleschen Funktionen einen formalen Beweis, dass Schaltkreise mit superlinearer Größe erfordert, d. $L = \{f_n\}_{n}$ $L$

, wobei .

S ⊢ \forall n \geq n_{0}, g (n) \cdot n \leq S (f_{n})

$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$

g (n) \in ω (1)

$g(n)\in \omega(1)$

Wenn wir als ausreichend groß, haben wir $n$

g (n) > c \cdot B B (T)

$g(n) > c\cdot BB(T)$

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

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?

cc.complexity-theory reference-request lo.logic circuit-complexity kolmogorov-complexity 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

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

(f (0, 0, . ., 0), f (0, 0, . ., 1), . ., f (1, 1, . ., 1))

$(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))$

$A(k)$ $K(A(k)) \geq k$ $k$ $K(A(k)) \geq k$

$BB(T)$

$\alpha(k)$ $k$ $\alpha(k)$ $K(0^{\alpha(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

B B (k)

$BB(k)$

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

Schaltkreisuntergrenzen und kolmogorov Komplexität

Antworten: