Verwendung der Kolmogorov-Komplexität als Eingangsgröße

Angenommen, wir haben ein Rechenproblem, z. B. 3-SAT, das eine Reihe von Probleminstanzen (mögliche Eingaben) . Normalerweise haben wir bei der Analyse von Algorithmen oder der Theorie der rechnerischen Komplexität einige Mengen aller Eingaben der Länge und eine Funktion , die die Laufzeit einiger Lösungsalgorithmen für die Eingabe . Die ungünstigste Laufzeitfolge für ist dann $S$

$$I(n) = \{w \in S : |w| = n\}$$ $n$$T(w)$$A$$w$$A$ $$f_n = \max_{w \in I(n)} T(w).$$

Definieren wir nun die Mengen aller Eingaben mit Kolmogorov-Komplexität und definieren wir die Folge Hier ist die durchschnittliche Laufzeitsequenz für , außer wenn die "Größe" der Eingaben ihre Kolmogorov-Komplexität ist, nicht ihre Länge.

$$I^K(n) = \{w \in S : K(w) = n \}$$ $n$fK $$f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w).$$ $f^K$$A$

Gibt es Algorithmen, bei denen sich asymptotisch signifikant von ? Wenn ja, gibt es Probleme, deren zeitliche Komplexität sich ändert, wenn diese andere Art der Analyse von Algorithmen verwendet wird?f K $f_n$$f^K_n$

Betrachten Sie die Paritätsfunktion (oder eine andere Funktion, die von allen / den meisten Bits der Eingabe abhängt). Für die Paritätsfunktion ist . Also Andererseits ist f n = Θ ( n ) . f K n = Θ ( $T(w) = \Theta(|w|)$

$$f_n = \Theta(n).$$ $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Man beachte, dass . Also und . In ähnlicher Weise ist ; somit wächst "sehr schnell". Außerdem ist es nicht schwer zu erkennen, dass es für keine berechenbare Obergrenze gibt .max w : K ( w ) = n | w | ≥ 2 2 Ω ( n ) , f K n ≥ 2 2 Ω ( n ) / 2 n → ∞ K ( 2 ... 2 2 n ) = O ( n ) f K $K(2^{2^n}) = O(n)$

$$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$$K(2^{\dots^{2^{2^n}}}) = O(n)$f K $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$$f_n^K$

Angesichts des Interesses an dieser Frage hielt ich es für hilfreich, den Grund, warum wir von der Antwort überhaupt nicht überrascht sein sollten, deutlicher herauszustellen und zu versuchen, eine Richtung für die Verfeinerung der Frage anzugeben. Dies sammelt und erweitert einige Kommentare. Ich entschuldige mich, wenn dies "offensichtlich" ist!

Betrachten Sie die Menge von Strings der Kolmogorov-Komplexität : Es gibt höchstens solcher Zeichenketten, da es Beschreibungen der Länge . Beachten Sie jedoch, dass diese Menge für das allgemeine unentscheidbar ist (andernfalls könnten wir berechnen, indem wir einfach von nach iterieren und die Zugehörigkeit zu überprüfen ). Weiterhin ist die Funktion wächst unberechenbar schnell. Es handelt sich um eine Variante der Besetzt-Biber-Funktion: Was ist die längste Ausgabe einer Turing-Maschine mit der BeschreibungslängeJ K ( n ) = { w : K ( w ) = n } . 2 n 2 n n n K ( w ) n = 1 | w | J K ( n ) g K ( n ) = max w ≤ J K ( n ) | w | n M M '$n$

$$J^K(n) = \{w : K(w) = n\}.$$ $2^n$$2^n$$n$$n$$K(w)$$n=1$$|w|$$J^K(n)$ $$g^K(n) = \max_{w \in J^K(n)} |w|$$ $n$? Wenn dies langsamer als irgendeine berechenbare Funktion wird, können wir das Problem des Anhaltens lösen: Wenn ein TM , konstruiere , das simuliert und bei jedem Schritt eine ausgibt. Wenn die Beschreibung Länge von ist , dann: stoppt in höchstens Schritte; oder hält nicht an.$M$$M'$$M$M ' n M g K ( n ) $1$$M'$$n$$M$$g^K(n)$$M$

Nun zu Andrews Frage: , wobei die Originalsprache ist. Die einzige Möglichkeit, zu vermeiden, dass Eingaben enthält, die in sehr groß sind, wäre, wenn nur sehr unkomprimierbare Zeichenfolgen enthält. (Beachten Sie, dass wir ansonsten die Unterscheidung zwischen Worst-Case- und Average-Case-Analyse völlig ignorieren können, da wir im Durchschnitt höchstens Zeichenfolgen verwenden, die Größe der größten Zeichenfolge jedoch schneller wächst als jede berechenbare Funktion von . )S I K ( n ) n S 2 n$I^K(n) = S \cap J^K(n)$$S$$I^K(n)$$n$$S$$2^n$$n$

Ich bin der Meinung, dass es wahrscheinlich unmöglich ist, ein nicht-triviales (dh unendliches) zu konstruieren , das nur unkomprimierbare Zeichenfolgen enthält und dennoch entscheidbar ist. Aber ich weiß es nicht. Aber hoffentlich gibt diese Intuition, warum sollten wir nicht für die meisten Sprachen hoffen haben wächst langsamer als eine berechenbare Funktion.f K $S$$f^K_n$

Um einen kleinen Schritt zurückzutreten, müssen Sie die Leistung für Eingaben der Länge mit der Leistung für Eingaben vergleichen, die auf die Länge komprimiert werden können . Wir haben jedoch Vorstellungen von Komprimierung, die weitaus besser handhabbar (und weniger leistungsfähig) sind als die Kolmogorov-Komplexität. Eine einfache Möglichkeit besteht darin, eine Schaltung der Größe zu geben , die bei Eingabe der Binärzahl das te Bit von . Beachten Sie, dass hier die Vergrößerung der Eingangsgröße höchstens exponentiell ist (ein Schaltkreis der Größe hat höchstens mögliche Eingänge).n n b b w n 2 $n$$n$$n$$b$$b$$w$$n$$2^n$

Also können wir die Frage umformulieren, indem wir Und definiere analog. Grund zur Hoffnung ist, dass die meisten Zeichenfolgen eine Schaltung benötigen, die fast so groß ist wie die Zeichenfolge selbst, und keine Zeichenfolge ist mehr als exponentiell größer als die erforderliche Schaltung. Vielleicht könnten wir in diesem Fall Sprachen finden, in denen und asymptotisch ähnlich sind.

$$I^C(n) = \{ w \in S : \text{the smallest circuit implicitly specifying $w$ has size $n$}\}.$$ $f^C_n$$f_n$$f^C_n$

Eine ziemlich verwandte Frage ist die Komplexität impliziter Sprachen wie IMPLICIT_SAT ist NEXP-vollständig, und normalerweise ist die implizite Version von NP-vollständigen Problemen NEXP-vollständig. Die Entscheidung für IMPLICIT_SAT ist mindestens so einfach wie die Verwendung der Schaltung zum Ausschreiben von und das Ausführen eines Algorithmus für SAT auf . Wenn also für SAT , scheint dies nahe daran zu liegen, zu beweisen, dass IMPLICIT_SAT im Durchschnitt fast so schnell entscheidbar ist wie SAT im schlechtesten Fall. Aber ich weiß nicht, wie man Ihren Begriff direkt mit impliziten Sprachen vergleichen würde, weil der Begriff "kleinster Stromkreis für

$$\mathsf{IMPLICIT\_SAT} = \{ \text{circuits $C$}: \text{$C$ implicitly specifies $w$}, w \in \mathsf{SAT}\}.$$ $w$$w$$f^C_n = \Theta(f_n)$$w$"kommt für implizite Sprachen nicht ins Spiel.

Hoffe das ist hilfreich / interessant!

Ich bin mir nicht sicher, ob in einem Lehrbuch implizite Probleme erwähnt werden, aber hier sind einige Vorlesungsunterlagen: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

Ein einfacher Fall scheint zu sein, in dem die Sprache nur aufgefüllte Instanzen enthält. Wenn aus einer Sprache indem jede Instanz der Größe mit Symbolen , kann im Bereich von .S L n 2 n - n f K n 2 f $S$$S$$L$$n$$2^n-n$$f^K_{n}$$2^{f_n}$