Kolmogorov Komplexitätsanwendungen in der rechnerischen Komplexität

Informell ausgedrückt ist die Kolmogorov-Komplexität eines Strings Länge eines kürzesten Programms, das x ausgibt . Wir können einen Begriff von 'zufälliger Zeichenfolge' definieren, indem wir ihn verwenden ( x ist zufällig, wenn K ( x ) ≥ 0,99 | x | ). Es ist leicht zu erkennen, dass die meisten Zeichenfolgen zufällig sind (es gibt nicht so viele kurze Programme).$x$$x$$x$$K(x) \geq 0.99 |x|$

Die Kolmogorov-Komplexitätstheorie und die algorithmische Informationstheorie sind heutzutage recht weit entwickelt. Und es gibt einige amüsante Beispiele für die Verwendung der Kolmogorov-Komplexität in Beweisen verschiedener Theoreme, die nichts über die Kolmogorov-Komplexität in ihren Aussagen enthalten ( konstruktive LLL , Loomis-Whitney-Ungleichung usw.).

Gibt es nette Anwendungen von Kolmogorov-Komplexität und algorithmischer Informationstheorie in der Komplexität von Rechnern und verwandten Gebieten ? Ich bin der Meinung, dass es Ergebnisse geben sollte, die die Komplexität von Kolmogorov als einfachen Ersatz für einfache Zählargumente verwenden. Das ist natürlich nicht so interessant.

Lance Fortnow hat einen Artikel zu diesem Thema geschrieben: Kolmogorov Complexity und Computational Complexity

Lesen Sie auch eine Einführung in die Kolmogorov-Komplexität und ihre Anwendungen von Li und Vitanyi, dem endgültigen Buch zu diesem Thema. Insbesondere werden in Kapitel 6 "Die Inkomprimierbarkeitsmethode" eine Reihe von Anwendungen in der Komplexität erörtert, beispielsweise ein Kolmogorov-Komplexitätsnachweis für Hastads Schalt-Lemma (aus Circuit Lower Bounds à la Kolmogorov von Fortnow und Laplante).

Und es gibt Anwendungen in der Kommunikationskomplexität (zB Kolmogorov-Komplexität und kombinatorische Methoden in der Kommunikationskomplexität von Kaplan und Laplante).

Erst vor wenigen Tagen hat Scott Aaronson anhand eines Arguments, das auf der Komplexität von Kolmogorov basiert, die Gleichwertigkeit von Stichproben und Suchen aufgezeigt . Ferner argumentiert er, dass in seinem Argument die Komplexität von Kolmogorov in einer wesentlichen Weise verwendet wird, die nicht nur eine Abkürzung für ein Zählargument ist.

Dieses Ergebnis von Alon et al. kann mit Hilfe von Kolmogorov Komplexität erhalten werden.

$\mathrm{poly}(\log |E|)$

Ein ausgezeichnetes Papier, das ich kenne (zusätzlich zu den anderen ausgezeichneten Papieren, die in anderen Antworten erwähnt wurden):

Juris Hartmanis, Verallgemeinerte Kolmogorov-Komplexität und die Struktur machbarer Berechnungen , FOCS 1983.

Die Hauptsache, an die ich mich aus diesem Aufsatz erinnere, ist eine auf Kolmogorovs Komplexität basierende Konstruktion eines Orakels, das P von NP trennt.

Ein anderes Papier, das mir in den Sinn kommt, ist

Allender et al., Power from Random Strings , FOCS 2002 ( ECCC-Version ) und SICOMP 2006 .

Wenn ich mich recht erinnere, trennt das letztere Papier die Vollständigkeit des Polynom-Time-Turing von der Vollständigkeit des Log-Space-Many-One in PSPACE unter Verwendung von Kolmogorov-Komplexitätsargumenten. Natürlich macht es viele andere Dinge, aber ich erinnere mich, dass die Trennung eine Anwendung ist, die von unabhängigem Interesse außerhalb der algorithmischen Informationstheorie ist.

Es gibt auch eine Quanten-Untergrenze-Technik, die die Kolmogorov-Komplexität nutzt:

" Untere Schranken für die Komplexität von Zufalls- und Quantenabfragen unter Verwendung von Kolmogorov-Argumenten " von Sophie Laplante und Frederic Magniez

$s$$K(s)$

(Nun zum Ernsthaften.) Daniil Musatov hat kürzlich gezeigt, dass naive Derandomisierung sinnvolle Konstruktionen für Objekte liefern kann, von denen normalerweise gezeigt wird, dass sie mit der probabilistischen Methode nicht konstruktiv existieren. Ich denke, dies wird wahrscheinlich signifikante zukünftige Anwendungen von ressourcengebundener Kolmogorov-Komplexität zu rechnerischer Komplexität liefern.

• Daniil Musatov, Verbesserung der raumgebundenen Version von Muchniks Bedingtem Komplexitätssatz durch naive Derandomisierung , CSR 2011, LNCS 6651, 64–76. doi: 10.1007 / 978-3-642-20712-9_6 ( Vordruck )

Siehe auch Artikel, in denen dieser zitiert wird .

(Bearbeiten: Verknüpfung zur späteren, veröffentlichten Version.)

H. Buhrman, L. Fortnow und S. Laplante. Resource-bounded Kolmogorov Komplexität überarbeitet. SIAM Journal on Computing, 31 (3): 887-905, 2002. ( Zeitschrift , Lances Webseite ).

Beinhaltet Anwendungen mit Kolmogorov-Komplexität wie:

• Ein Beweis von Valiant-Vazirani
• Befriedigende Zuordnungen von Booleschen Formeln können in der Ausgabegröße zeitpolynomisch aufgezählt werden, wenn eine eindeutige Zuordnung schnell gefunden werden kann
• Ein neuer Beweis, dass BPP in Sigma_2 P ist
• Mehrere Orakelbauten

Einige der obigen Aussagen wurden erstmals in dieser Arbeit bewiesen, während andere lediglich neue Beweise für alte Theoreme sind, die die Komplexität von Kolmogorov verwenden.

Anwendungen der zeitgebundenen Kolmogorov-Komplexität in der Komplexitätstheorie sind eine schöne Übersicht von Eric Allender über andere Anwendungen. Obwohl viele der Ergebnisse hier Auswirkungen haben, handelt es sich bei einigen um echte Anwendungen, wie zum Beispiel die folgenden:

• Cor 13: Gegenüber einem generischen Orakel gibt es keinen Pseudozufallsgenerator, der gegen P / Poly-Gegner sicher ist.
• Thm 16 [Allender und Gore, 1991]: Es gibt ein Orakel, zu dem alle NE-Prädikate in Exponentialzeit und E = Union_k \ Sigma_k-TIME (n) lösbar sind.

Beide Beweise verwenden Kolmogorov Komplexität erheblich.

$D$$D$

Die minimale Beschreibungslänge verwendet die Kolmogorov-Komplexität (oder deren Annäherungen und Verallgemeinerungen aufgrund der Unentscheidbarkeit) im informationstheoretischen Lernen und in der Inferenztheorie. Insbesondere wird MDL verwendet, um Erklärungen für Daten zu finden, die natürlich eine Überanpassung vermeiden.

Jorma Rissanen bietet eine gute Einführung in sein Konzept: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

Meinen Sie so etwas, Ilyaraz?

http://arxiv.org/abs/1004.3993