Rozkłady prawdopodobieństwa i złożoność obliczeniowa

To pytanie dotyczy przecięcia teorii prawdopodobieństwa i złożoności obliczeniowej. Jednym kluczowym spostrzeżeniem jest to, że niektóre rozkłady są łatwiejsze do wygenerowania niż inne. Na przykład problem

Biorąc pod uwagę liczbę $n$ , zwróć równomiernie rozłożoną liczbę $i$ z $0 \leq i < n$ .

jest łatwy do rozwiązania. Z drugiej strony, następujący problem jest lub wydaje się być znacznie trudniejszy.

Biorąc pod uwagę liczbę $n$ , zwróć liczbę $i$ takie, że $i$ jest (liczba Gödla) ważnym dowodem długości n w arytmetyce Peano. Ponadto, jeśli liczba takich dowodów wynosi $pr(n)$ , to prawdopodobieństwo uzyskania konkretnego dowodu długości $n$ Powinien być $\frac{1}{pr(n)}$ .

To sugeruje mi, że rozkłady prawdopodobieństwa mają pojęcie złożoności obliczeniowej. Co więcej, ta złożoność jest prawdopodobnie ściśle związana z podstawowymi problemami decyzyjnymi (czy to sub-rekurencyjnymi, np $P$ , $EXP$ , rekurencyjne, rekurencyjnie policzalne lub gorzej).

Moje pytanie brzmi: w jaki sposób definiuje się złożoność obliczeniową rozkładów prawdopodobieństwa, szczególnie tam, gdzie leżący u podstaw problem decyzyjny nie jest rozstrzygalny. Jestem pewien, że zostało to już zbadane, ale nie jestem pewien, gdzie szukać.

complexity-theory reference-request probability-theory probabilistic-algorithms Martin Berger
źródło

Innym interesującym przykładem (ale który można rozstrzygać) jest kwantowa transformata Fouriera. Biorąc pod uwagę zwraca liczbę tak, że prawdopodobieństwo jest proporcjonalne do, .

f (k) = a^{k} \mod b

$f(k)=a^k \mod b$

l \in [0, N]

$l \in [0,N]$

l

$l$

| F (l) |

$\left|F(l)\right|$

F (l) = \sum_{k = 0}^{N} f (k) e^{- 2 π i k l / N}

$F(l) = \sum_{k=0}^N f(k) e^{-2\pi ikl/N}$

Wandering Logic

Oba twoje przykłady są dyskretnymi jednorodnymi rozkładami. Wyobrażam sobie, jak różne byłyby złożoności tego, jak trudno policzyćgdzie jest wsparciem.

| χ |

$|\chi|$

χ

$\chi$

Nicholas Mancuso

@NicholasMancuso Zgadzam się, że zawsze można zastosować liczenie + nieformalny wybór. W pewnym sensie daje to górną granicę. Czy to wszystko, co można powiedzieć? Gdzie w literaturze zostało to zbadane?

Martin Berger

@NicholasMancuso Podane przeze mnie przykłady to jednolite rozkłady. Ale można zadać to samo pytanie o nierównomierne rozkłady. Można również zastanawiać się nad dystrybucjami na . Jeśli chodzi o rozkłady dyskretne: prima facie, liczenie nie wydaje się ogólnie wystarczające, musisz także być w stanie wygenerować -ty element, po jednolitym wybraniu . To powiedziawszy, być może liczenie jest rdzeniem problemu.

R

$\mathbb{R}$

i

$i$

i

$i$

Martin Berger,

@NikosM. Dzięki, ale ten link też nie mówi nic o złożoności podstawowej dystrybucji. Referencje mówią o transformacji w rozkładzie jednolitym. Ale ta transformacja może być trudna / lub łatwa obliczeniowo.

ϕ

$\phi$

Martin Berger

Złożoność rozkładów prawdopodobieństwa pojawia się szczególnie w badaniu problemów dystrybucyjnych takich jak DistNP w teorii Levina w teorii średniej złożoności przypadków .

Rozkład można obliczyć P, jeśli jego funkcję gęstości skumulowanej można oszacować w czasie wielomianowym.

Rozkład jest P-samplable, jeśli możemy próbkować z nich w czasie wielomianowym.

Jeśli rozkład jest obliczalny dla P, to jest on samp-podobny. Odwrotna sytuacja nie jest prawdą, jeśli istnieją pewne funkcje jednokierunkowe.

Możesz rozszerzyć definicje na inne klasy złożoności.

Oded Goldreich ma ładne notatki wprowadzające na ten temat, które możesz chcieć sprawdzić.

Kaveh
źródło

Dzięki, myślę, że teoria rozkładów w jest czymś, czego szukałem. Ale nie ma powodu, aby ograniczać uwagę na , można określić -samplable rozkładów dla każdej klasy złożoność . Wraz z pojawieniem się probabilistycznych języków programowania, które staje się niezbędne.

P

$P$

P

$P$

C

$C$

C

$C$

Martin Berger,

@Martin, tak. Podczas NIPS 2015 odbył się samouczek na temat programowania probabilistycznego ( slajdy , wideo też zostanie opublikowane). Miło widzieć ludzi pracujących na skrzyżowaniu ML / Stats i PL. :)

Kaveh

Tak, a głównym problemem jest to, że takie języki (= ogólne, programowalne samplery) są wolne. Jak możemy je przyspieszyć?

Martin Berger

Rozkłady prawdopodobieństwa i złożoność obliczeniowa

Odpowiedzi: