Czy istnieje uogólnienie teorii informacji na wielomianowo poznaną informację?

Przepraszam, to trochę „miękkie” pytanie.

Teoria informacji nie ma pojęcia złożoności obliczeniowej. Na przykład instancja SAT lub instancja SAT plus bit wskazujący na satysfakcję niosą tę samą ilość informacji.

Czy istnieje sposób sformalizowania pojęcia „wielomianowo poznawalny”?

Takie ramy mogą definiować na przykład pojęcie dywergencji wielomianowej KL między zmienną losową X względem Y jako liczbę bitów potrzebną do obliczenia X w czasie wielomianowym dla Y.

Podobnie, entropia zmiennej losowej X może być zdefiniowana jako liczba bitów potrzebna do zakodowania X w sposób, który można dekodować w czasie wielomianowym.

Czy badano takie uogólnienie? Czy można to uczynić spójnym?

Tak. Ograniczona w czasie złożoność Kołmogorowa jest co najmniej jednym z takich „uogólnień” (choć ściśle mówiąc, nie jest to uogólnienie, ale związana z nim koncepcja). Fix uniwersalną maszynę Turinga . -czas-ograniczona Kołmogorowa złożoność łańcucha podanego łańcucha (w stosunku do ), oznaczony (indeks często stłumione) jest zdefiniowana jako najkrótszego łańcucha ( „program” dla ) taki, że i taki, że obliczenie zajmuje co najwyżej$U$$t(n)$$x$$y$$U$$K^t_U(x | y)$$U$$p$$U$$U(p,y)=x$$U(p,y)$$t(|x|)$czas. Jeśli weźmiesz to za swoją definicję „informacji warunkowej”, możesz również zdefiniować wszystkie zwykłe pojęcia z teorii informacji.

Jednak w tym ograniczonym czasowo otoczeniu nie są znane wszystkie typowe twierdzenia teorii informacji. Na przykład wiadomo, że symetria informacji utrzymuje się dla zwykłej złożoności Kołmogorowa (bez ograniczenia czasowego), ale nie jest znana z tego, że ogranicza czas. Zobacz na przykład rozdział 6 rozprawy Troya Lee .

Jeśli obawiasz się, że dotyczy to łańcuchów, a nie rozkładów, sugeruję przeczytanie następujących artykułów, które mówią, że w rzeczywistości złożoność łańcuchów Kołmogorowa i entropia rozkładów Shannona są bardzo ściśle powiązane:

• Grunwald i Vitanyi. Informacje Shannona i złożoność Kołmogorowa

• Hammer, Romashchenko, Shen, Vereshchagin. Nierówności dla złożoności Shannona Entropii i Kołmogorowa .

(Z drugiej strony istnieją pewne właściwości, o których wiadomo, że nie są dzielone między nimi, patrz Muchnik i Vereshchagin, Shannon Entropy vs. Złożoność Kołmogorowa .)

Jednym z problemów jest to, że wiele twierdzeń, do których jesteśmy przyzwyczajeni w teorii informacji, nie ma zastosowania w świecie obliczeniowym. Dlatego nawet jeśli sformalizujemy obliczeniowy analog entropii, wynikowa teoria może już nie przypominać teorii informacji.

Na przykład, jeśli jest funkcją deterministyczną, to . Jednak w przypadku jakiegokolwiek prawdopodobnego obliczeniowego pojęcia entropii nie będzie to dłużej obowiązywać: pomyśl na przykład generator pseudolosowy, który rozciąga krótkie ziarno do długiego pseudolosowego wyniku. Z dowolnej wyobrażalnej definicji entropii obliczeniowej mogę sobie wyobrazić, że długi wynik pseudolosowy będzie miał dużą entropię obliczeniową (jest obliczeniowo nie do odróżnienia od jednolitego rozkładu na tych długich łańcuchach), naruszając w ten sposób .$f$$H(f(X)) \le H(X)$$H(f(X)) \le H(X)$

Nie jestem świadomy teoretycznego modelu obliczeniowego informacji, ale istnieją wyraźne zastosowania teorii informacji do złożoności obliczeniowej.

Na przykład klasyczna dolna granica sortowania opartego na porównaniu opiera się na teoretycznym argumencie dotyczącym wysokości drzewa decyzyjnego potrzebnym do rozróżnienia wszystkich możliwych rzędów danych wejściowych. Podobnie możesz tworzyć trywialne teoretyczne granice informacji dotyczące złożoności obliczeniowej wyszukiwania, statystyki zamówień, średniej itp.$n \log n$

Częściej wyniki teoretyczne mogą służyć jako dolne granice złożoności obliczeniowej. Na przykład „teoretyczny” wynik Yao dotyczący złożoności komunikacji {1} implikuje obliczeniowe dolne granice przy określaniu, czy dwa zestawy są równe. Bardziej zaawansowane zastosowania złożoności komunikacyjnej zapewniają kompromisy czasowo-przestrzenne dla maszyn Turinga {2}.

{1} Yao, Andrew Chi-Chih. „Niektóre pytania dotyczące złożoności związane z obliczeniami dystrybucyjnymi (raport wstępny)”. Materiały jedenastego dorocznego sympozjum ACM na temat teorii obliczeń. ACM, 1979.

{2} Eyal Kushilevitz: złożoność komunikacji. Advances in Computers 44: 331-360 (1997).