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

— 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