Gibt es eine Verallgemeinerung der Informationstheorie auf polynomiell erkennbare Informationen?

9

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?

cc.complexity-theory it.information-theory polynomial-time Arthur B.
quelle

1

Haben Sie versucht, dies auf Cryptography SE crypto.stackexchange.com zu erfragen ?

Zsbán Ambrus

2

Es ist möglich, dass die Krypto-Leute eine Antwort haben, aber die Frage ist hier perfekt zum Thema, und ich vermute, dass es eine bessere Chance gibt, hier eine gute Antwort zu bekommen. Nur eine kurze Anmerkung: Bitte stellen Sie nicht dieselbe Frage erneut auf Crypto.SE. Cross-Posting auf mehreren SE-Sites ist nach Site-Regeln verboten.

DW

9

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 -zeitbegrenzte Kolmogorov-Komplexität eines Strings bei einem String (relativ zu ), der mit (der Index wird häufig unterdrückt), wird als der kürzeste String ( ein "Programm" für ), so dass $U$ $t(n)$ $x$ $y$ $U$ $K^t_U(x | y)$ $U$ $p$ $U$ und so, dass die Berechnung von höchstens 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 .)

Joshua Grochow
quelle

Mein Hauptanliegen wäre, dass die Zeit von Turing Machine abhängt. Da Turing-Maschinen sich höchstens mit einer polynomiellen Beschleunigung oder Beschleunigung gegenseitig emulieren können, scheint eine Bestrafung der Komplexität durch log (log (t)) sie bis zu einer additiven Konstante äquivalent zu machen. Die Komplexität von Levin verwendet jedoch log (t). Ich bin mir nicht sicher, warum.

Arthur B

1

t (n)

$t(n)$

\log \log t

$\log \log t$

2

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.

$f$ $H(f(X)) \le H(X)$ $H(f(X)) \le H(X)$

DW
quelle

Ich verstehe, ich frage mich nur, wie viel gerettet oder geflickt werden kann. In diesem Fall könnten Sie die Einschränkung hinzufügen, dass f polynomiell invertierbar ist, aber das fühlt sich ad-hoc an

Arthur B

Ich glaube, der Startwert enthält mehr Informationen als die generierte pseudozufällige Zeichenfolge, da wir die generierte Zeichenfolge aus dem Startwert berechnen können.

Kaveh

@Kaveh, wenn Sie in einem informationstheoretischen Sinne sprechen: Wenn der Pseudozufallsgenerator invertierbar ist (möglicherweise nicht in Polynomzeit, aber im Prinzip), dann haben seine Eingabe und Ausgabe die gleiche Menge an Informationen, informationstheoretisch; Andernfalls haben Sie Recht, wenn das pseudozufällige Subjekt nicht invertierbar ist.

DW

0

Mir ist kein informationstheroetisches Rechenmodell bekannt, aber es gibt klare Anwendungen der Informationstheorie auf die Komplexität der Berechnungen.

$n \log n$

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).

Ari Trachtenberg
quelle

Gibt es eine Verallgemeinerung der Informationstheorie auf polynomiell erkennbare Informationen?

Antworten: