Zastosowania złożoności Kołmogorowa w złożoności obliczeniowej

Nieformalnie mówiąc, złożoność Kołmogorowa ciągu jest długością najkrótszego programu, który wypisuje . Możemy zdefiniować pojęcie „losowego ciągu” używając go ( jest losowy, jeśli ) Łatwo jest zauważyć, że większość ciągów jest losowa (nie ma tak wielu krótkich programów).x x K ( x ) ≥ 0,99 | x $x$$x$$x$$K(x) \geq 0.99 |x|$

Teoria złożoności Kołmogorowa i algorytmiczna teoria informacji są obecnie dość rozwinięte. Istnieje kilka zabawnych przykładów użycia złożoności Kołmogorowa w dowodach różnych twierdzeń, które nie zawierają niczego w złożoności Kołmogorowa w ich wypowiedziach ( konstruktywna LLL , nierówność Loomisa-Whitneya i tak dalej).

Czy są jakieś ładne zastosowania złożoności Kołmogorowa i algorytmicznej teorii informacji w złożoności obliczeniowej i powiązanych dziedzinach ? Uważam, że powinny istnieć wyniki, które wykorzystują złożoność Kołmogorowa jako proste zastąpienie prostych argumentów liczenia. To oczywiście nie jest interesujące.

Lance Fortnow napisał artykuł na ten temat: Złożoność Kołmogorowa i złożoność obliczeniowa

Powinieneś także zapoznać się z Wstępem do złożoności Kołmogorowa i jego zastosowaniami Li i Vitanyi, ostateczną książką na ten temat. W szczególności rozdział 6 „Metoda nieściśliwości” omawia wiele złożonych aplikacji, takich jak dowody złożoności Kołmogorowa na lemat przełączający Hastada (z Circuit Lower Bounds à la Kolmogorov autorstwa Fortnow i Laplante).

Istnieją również zastosowania w złożoności komunikacji (np. Złożoność Kołmogorowa i metody kombinatoryczne w złożoności komunikacji autorstwa Kaplana i Laplante).

Jeszcze kilka dni temu Scott Aaronson wykorzystał argument oparty na złożoności Kołmogorowa, aby wykazać równoważność pobierania próbek i wyszukiwania . Dalej twierdzi, że w jego argumencie złożoność Kołmogorowa jest wykorzystywana w istotny sposób, który nie jest jedynie skrótem do liczenia argumentu.

Ten wynik Alon i in. można uzyskać za pomocą złożoności Kołmogorowa.

„Zestaw krawędzi E każdego skończonego dwustronnego wykresu można podzielić na podzbiory , aby wszystkie powstałe wykresy dwudzielne były prawie regularne”.$\mathrm{poly}(\log |E|)$

Jeden doskonały artykuł, który znam (oprócz tych innych doskonałych artykułów wymienionych w innych odpowiedziach):

Juris Hartmanis, Uogólniona złożoność Kołmogorowa i struktura wykonalnych obliczeń , FOCS 1983.

Najważniejszą rzeczą, którą pamiętam z tego artykułu, jest złożona z Kołmogorowa konstrukcja wyroczni oddzielającej P od NP.

Kolejny artykuł, który przychodzi mi na myśl, to

Allender i wsp., Power from Random Strings , FOCS 2002 ( wersja ECCC ) i SICOMP 2006 .

O ile pamiętam, ten ostatni artykuł oddziela kompletność Turinga w czasie wielomianowym od kompletności wielokrotności logarytmicznej w przestrzeni PSPACE, używając argumentów złożoności Kołmogorowa. Oczywiście robi wiele innych rzeczy, ale pamiętam, że separacja jest jedną aplikacją, która jest niezależna od niezależnych algorytmicznych teorii informacji.

Istnieje również kwantowa technika dolnej granicy, która wykorzystuje złożoność Kołmogorowa:

„ Dolne granice losowości i kwantowej złożoności zapytań z wykorzystaniem argumentów Kołmogorowa ” Sophie Laplante i Frederic Magniez

(Po pierwsze, jest żart.) W obliczu trudnego problemu złożoności obliczeniowej zawsze jest radość z zastosowania złożoności Kołmogorowa, aby podnieść na duchu. Jest to również znane jako golf golfowy . W przypadku szeregu drobnych problemów odpowiadających ciągom , można zbadać wewnętrzną złożoność konkurencyjny na stronie http://codegolf.com/ lub po prostu dla zabawy na stronie http://golf.shinh.org/ (z 80 różnymi języki w tym ostatnim miejscu, dla których należy oszacować stałe twierdzenia niezmienniczości). Podobnie jak w przypadku wszystkich nierozstrzygalnych funkcji, należy zachować ostrożność.K ( s $s$$K(s)$

(Teraz na poważnie.) Daniil Musatov ostatnio wykazał, że naiwna derandomizacja może zapewnić rozsądne konstrukcje dla obiektów, które zwykle okazują się niekonstruktywne za pomocą metody probabilistycznej. Myślę, że prawdopodobnie zapewni to znaczące przyszłe zastosowania złożoności złożoności Kołmogorowa do złożoności obliczeniowej.

• Daniil Musatov, Poprawianie ograniczonej przestrzennie wersji twierdzenia Muchnika o warunkowej złożoności poprzez derandomizację naiwną , CSR 2011, LNCS 6651, 64–76. doi: 10.1007 / 978-3-642-20712-9_6 ( preprint )

Zobacz także artykuły powołujące się na ten .

(Edycja: link do późniejszej opublikowanej wersji).

H. Buhrman, L. Fortnow i S. Laplante. Ponownie przeanalizowano złożoność złożoności Kołmogorowa. SIAM Journal on Computing, 31 (3): 887-905, 2002. ( czasopismo , strona internetowa Lance'a ).

Obejmuje zastosowania złożoności Kołmogorowa, takie jak:

• Dowód Valiant-Vazirani
• Spełniające przypisania formuł boolowskich można wyliczyć w postaci wielomianu czasowego w wielkości wyjściowej i jeśli unikalne przypisanie można szybko znaleźć
• Nowy dowód, że BPP jest w Sigma_2 P.
• Kilka konstrukcji wyroczni

Niektóre z powyższych zostały po raz pierwszy udowodnione w tym artykule, podczas gdy inne są po prostu nowymi dowodami starych twierdzeń, wykorzystującymi złożoność Kołmogorowa.

Zastosowanie ograniczonej czasowo złożoności Kołmogorowa w teorii złożoności to miła ankieta przeprowadzona przez Erica Allendera z innych aplikacji. Chociaż wiele wyników tutaj jest implikacjami, niektóre są prawdziwymi zastosowaniami, takimi jak:

• Cor 13: W stosunku do ogólnej wyroczni nie ma generatora pseudolosowego, który byłby zabezpieczony przed przeciwnikami P / poli.
• Thm 16 [Allender and Gore, 1991]: Istnieje wyrocznia, w stosunku do której wszystkie predykaty NE można rozwiązać w czasie wykładniczym, a E = Union_k \ Sigma_k-TIME (n).

Oba dowody znacznie wykorzystują złożoność Kołmogorowa.

Jednym z przykładów jest następujący wynik opisany w ankiecie przeprowadzonej przez Bogdanova i Trevisana : istnieje rozkład taki, że język jest średnio łatwy w odniesieniu do jeśli jest najgorszy w najprostszym przypadku.$D$$D$

Minimalna długość opisu wykorzystuje złożoność Kołmogorowa (lub jego przybliżenia i uogólnienia z powodu nierozstrzygalności) w uczeniu się informacji teoretycznej i teorii wnioskowania. W szczególności MDL służy do znajdowania wyjaśnień dotyczących danych, które w naturalny sposób unikają nadmiernego dopasowania.

Jorma Rissanen zapewnia dobre wprowadzenie do swojej koncepcji: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

Masz na myśli coś takiego, ilyaraz?

http://arxiv.org/abs/1004.3993