Ich entschuldige mich, das ist eine "weiche" Frage.
Die Informationstheorie hat kein Konzept der rechnerischen Komplexität. Beispielsweise enthält eine Instanz von SAT oder eine Instanz von SAT plus ein Bit, das die Erfüllbarkeit anzeigt, dieselbe Informationsmenge.
Gibt es eine Möglichkeit, das Konzept des "polynomiell erkennbaren" zu formalisieren?
Ein solches Framework könnte beispielsweise den Begriff der Polynom-KL-Divergenz zwischen einer Zufallsvariablen X relativ Y als die Anzahl der Bits definieren, die zur Berechnung von X in der Polynomzeit bei Y benötigt werden.
Ebenso könnte die Entropie einer Zufallsvariablen X als die Anzahl der Bits definiert werden, die benötigt werden, um X auf eine Weise zu codieren, die in Polynomzeit decodiert werden kann.
Wurde eine solche Verallgemeinerung untersucht? Kann es konsistent gemacht werden?
Antworten:
Ja. Die zeitlich begrenzte Kolmogorov-Komplexität ist mindestens eine solche "Verallgemeinerung" (obwohl es streng genommen keine Verallgemeinerung, sondern ein verwandtes Konzept ist). Fix eine universelle Turing - Maschine . Die t ( n ) -zeitbegrenzte Kolmogorov-Komplexität eines Strings x bei einem String y (relativ zu U ), der mit K t U ( x | y ) bezeichnet wird (der Index U wird häufig unterdrückt), wird als der kürzeste String p ( ein "Programm" für U ), so dass U ( p , yU. t ( n ) x y U. K.tU.( x | y) U. p U. und so, dass die Berechnung von U ( p , y ) höchstens t ( | x | ) Zeit benötigt. Wenn Sie dies als Ihre Definition von "bedingter Information" nehmen, können Sie ebenfalls alle üblichen Konzepte aus der Informationstheorie definieren.U.( p , y) = x U.( p , y) t ( | x | )
In dieser zeitlich begrenzten Umgebung sind jedoch nicht alle üblichen Theoreme der Informationstheorie bekannt. Beispielsweise ist bekannt, dass die Symmetrie von Informationen für die übliche Kolmogorov-Komplexität gilt (nicht zeitgebunden), nicht jedoch für die zeitgebundene. Siehe zum Beispiel Kapitel 6 von Troy Lees These .
Wenn Sie befürchten, dass dies eher für Zeichenfolgen als für Verteilungen gilt, empfehle ich Ihnen, die folgenden Artikel zu lesen, in denen festgestellt wird, dass die Kolmogorov-Komplexität von Zeichenfolgen und die Shannon-Entropie von Verteilungen sehr eng miteinander verbunden sind:
Grunwald und Vitanyi. Shannon Information und Kolmogorov-Komplexität
Hammer, Romashchenko, Shen, Vereshchagin. Ungleichungen für Shannon-Entropie und Kolmogorov-Komplexität .
(Auf der anderen Seite gibt es einige Eigenschaften, von denen bekannt ist, dass sie nicht zwischen beiden geteilt werden, siehe Muchnik & Vereshchagin, Shannon Entropy vs. Kolmogorov Complexity .)
quelle
Ein Problem ist, dass viele der Theoreme, die wir in der Informationstheorie gewohnt sind, nicht in der Computerwelt gelten. Selbst wenn wir ein rechnerisches Analogon der Entropie formalisieren würden, könnte die resultierende Theorie daher nicht mehr wie die Informationstheorie aussehen.
quelle
Mir ist kein informationstheroetisches Rechenmodell bekannt, aber es gibt klare Anwendungen der Informationstheorie auf die Komplexität der Berechnungen.
Typischerweise können informationstheoretische Ergebnisse als Untergrenzen für die Komplexität der Berechnungen dienen. Zum Beispiel impliziert Yaos "informationstheoretisches" Ergebnis zur Kommunikationskomplexität {1} rechnerische Untergrenzen für die Bestimmung, ob zwei Mengen gleich sind. Anspruchsvollere Anwendungen der Kommunikationskomplexität bieten Zeit-Raum-Kompromisse für Turing-Maschinen {2}.
{1} Yao, Andrew Chi-Chih. "Einige Komplexitätsfragen im Zusammenhang mit Distributive Computing (vorläufiger Bericht)." Vorträge des elften jährlichen ACM-Symposiums zur Theorie des Rechnens. ACM, 1979.
{2} Eyal Kushilevitz: Kommunikationskomplexität. Advances in Computers 44: 331 & ndash; 360 (1997).
quelle