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

44

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

— ilyaraz
źródło

2

Czy szukasz tylko przykładów problemów, które na pierwszy rzut oka wydają się nie mieć nic wspólnego ze złożonością Kołmogorowa? Istnieje wiele wyników dotyczących złożoności obliczeniowej różnych zbiorów zdefiniowanych w kategoriach złożoności Kołmogorowa (w szczególności zestaw ciągów losowych Kołmogorowa), a także wiele wyników dotyczących związanej z zasobami złożoności Kołmogorowa ze standardowymi rzeczami złożoności (np. P vs NP , faktoring itp.). Ale nie jestem pewien, czy te ostatnie są tym, czego szukasz, czy nie.

— Joshua Grochow

1

> Czy szukasz tylko przykładów problemów, które początkowo wydają się nie mieć nic wspólnego ze złożonością Kołmogorowa? Dokładnie tak.

— ilyaraz,

16

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

— Ian
źródło

1

Dziękuję Ci. Ten artykuł jest bardzo ładny i użyteczny, ale chcę, aby aplikacje nie wspominały o złożoności K w instrukcjach.

— ilyaraz,

1

ilyaraz, chociaż większość wyników wymienionych w tym artykule jest implikacjami, a nie aplikacjami, można uznać charakterystykę klas złożoności według złożoności Kołmogorowa za słabą formę „aplikacji”.

— Joshua Grochow

Zaktualizowałem post, dodając kilka referencji, które mogą być bardziej zgodne z tym, czego szukasz.

— Ian

14

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.

— Martin Schwarz
źródło

11

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

— ilyaraz
źródło

wydaje się sprzeczne z intuicją. czy ktoś wie o innych wynikach dotyczących wykresów dwustronnych i zwykłych?

— vzn

11

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.

— Dave Doty
źródło

9

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

— Robin Kothari
źródło

9

(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ść. $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).

— András Salamon
źródło

1

Powiedziałbym, że ten ostatni artykuł stosuje złożoność obliczeniową (mianowicie generator pseudolosowy Nisana) do złożoności złożoności Kołmogorowa, a nie odwrotnie.

— ilyaraz

1

@ilyaraz: To dokładne podsumowanie. Mówię, że biorąc pod uwagę linki w jednym kierunku, powinno być możliwe, aby te aplikacje działały również w drugą stronę.

— András Salamon

8

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.

— Joshua Grochow
źródło

Wydaje mi się, że oryginalny dowód Sipsera, że „BPP jest w Sigma_2”, wykorzystywał złożoność Kołmogorowa.

— ilyaraz,

6

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$

— ilyaraz
źródło

Nawiasem mówiąc, ta wersja ankiety ma wadę. Można to jednak naprawić :)

— Grigorij Jarosławcew

Możesz rozwinąć temat?

— ilyaraz

Nawiasem mówiąc, mam dziwne przeczucie, że mogę wyostrzyć ten dowód: można się pozbyć i postawić tam jakieś podświadome prawdopodobieństwo. Jestem ciekawy, gdzie jest błąd.

1 / n^{3}

$1/n^3$

— ilyaraz

Tak. Znalazłem błąd, ale wydaje mi się, że mam bardziej intuicyjny dowód (z ).

1 / n^{1 + ϵ}

$1/n^{1 + \epsilon}$

— ilyaraz

5

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

— Ross Snider
źródło

3

Masz na myśli coś takiego, ilyaraz?

http://arxiv.org/abs/1004.3993

— Aaron Sterling
źródło

Tak, wydaje się zachęcające.

— ilyaraz,