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

9

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?

cc.complexity-theory it.information-theory polynomial-time

— Artur B.
źródło

1

Czy próbowałeś o to zapytać na Cryptography SE crypto.stackexchange.com ?

— Zsbán Ambrus

2

Możliwe, że krypto-ludzie mogą znaleźć odpowiedź, ale pytanie jest tutaj idealnie na temat i podejrzewam, że może mieć większą szansę na uzyskanie dobrej odpowiedzi tutaj. Krótka uwaga: nie wysyłaj ponownie tego samego pytania na Crypto.SE; zamieszczanie postów w wielu witrynach SE jest zabronione przez reguły witryny.

— DW

9

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

— Joshua Grochow
źródło

Moim głównym zmartwieniem byłoby to, że czas zależy od maszyny Turinga. Ponieważ maszyny Turinga mogą emulować się nawzajem z co najwyżej wielomianowym przyspieszaniem lub zwalnianiem, karanie złożoności przez log (log (t)) wydaje się równoważyć je do stałej addytywnej. Jednak złożoność Levina wykorzystuje log (t), nie jestem pewien dlaczego.

— Arthur B

1

@Arthur B: Rozumiem twoją troskę, ale prawdopodobnie istnieje na to kilka standardowych sposobów. Zazwyczaj, gdy udowodnisz stwierdzenie dotyczące np. Ograniczonej czasowo złożoności Kołmogorowa, możesz udowodnić stwierdzenie o formie „dla wszystkich wielomianowych granic czasowych , ...”, w którym to momencie dowolne wielomianowe spowolnienie / prędkość -up poniesione przez zmianę uniwersalnej maszyny nie jest już istotne, ponieważ oświadczenie ma zastosowanie w każdym przypadku. (Nie podążałem za tym, co mówiłeś o , ale myślę, że to tylko inny sposób, aby spróbować poradzić sobie z tym problemem ...)

t (n)

$t(n)$

\log \log t

$\log \log t$

— Joshua Grochow

2

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

— DW
źródło

Rozumiem, po prostu zastanawiam się, ile można uratować lub załatać. W takim przypadku możesz dodać ograniczenie, że f jest wielomianowo odwracalny, ale wydaje się to ad hoc

— Arthur B

Wydaje mi się, że ziarno zawiera więcej informacji niż wygenerowany ciąg losowy psuedo, ponieważ możemy obliczyć wygenerowany ciąg z nasion.

— Kaveh

@Kaveh, jeśli mówisz w sensie teoretycznym: jeśli generator pseudolosowy jest odwracalny (może nie w czasie wielomianowym, ale w zasadzie), wówczas jego dane wejściowe i wyjściowe mają taką samą ilość informacji, teoretycznie; w przeciwnym razie, jeśli pseudolosowy podmiot jest nieodwracalny, masz rację.

— DW

0

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

— Ari Trachtenberg
źródło