Wahrscheinlichkeitsverteilungen und Rechenkomplexität

Diese Frage betrifft die Schnittstelle von Wahrscheinlichkeitstheorie und Rechenkomplexität. Eine wichtige Beobachtung ist, dass einige Verteilungen einfacher zu generieren sind als andere. Zum Beispiel das Problem

Geben Sie bei einer gegebenen Zahl eine gleichmäßig verteilte Zahl mit $n$ $i$ $0 \leq i < n$ .

ist leicht zu lösen. Andererseits ist oder scheint das folgende Problem viel schwieriger zu sein.

Geben Sie bei einer gegebenen Zahl eine Zahl so dass (die Gödel-Zahl von) ein gültiger Beweis für die Länge n in der Peano-Arithmetik ist. Wenn die Anzahl solcher Beweise , sollte die Wahrscheinlichkeit, einen spezifischen Beweis der Länge zu erhalten, $n$ $i$ $i$ $pr(n)$ $n$ . $\frac{1}{pr(n)}$

Dies legt für mich nahe, dass Wahrscheinlichkeitsverteilungen mit einem Begriff der rechnerischen Komplexität einhergehen. Darüber hinaus hängt diese Komplexität wahrscheinlich eng mit den zugrunde liegenden Entscheidungsproblemen zusammen (ob subrekursiv, z. B. , , rekursiv, rekursiv aufzählbar oder schlimmer). $P$ $EXP$

Meine Frage ist: Wie definiert man die rechnerische Komplexität von Wahrscheinlichkeitsverteilungen, insbesondere wenn das zugrunde liegende Entscheidungsproblem nicht entscheidbar ist? Ich bin mir sicher, dass dies bereits untersucht wurde, aber ich bin mir nicht sicher, wo ich suchen soll.

complexity-theory reference-request probability-theory probabilistic-algorithms Martin Berger
quelle

Ein weiteres interessantes Beispiel (das aber entscheidbar ist) ist die Quanten-Fourier-Transformation. Gegeben ist

eine Zahl

so dass die Wahrscheinlichkeit von

proportional zu

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

Beide Beispiele sind diskrete Gleichverteilungen. Ich würde mir vorstellen, dass die unterschiedlichen Komplexitäten darin bestehen, wie schwer es ist,

zu zählen

| χ |

$|\chi|$

χ

$\chi$ ist die Unterstützung.

Nicholas Mancuso

@NicholasMancuso Ich stimme zu, dass Zählen + unformierte Auswahl immer verwendet werden kann. In gewissem Sinne gibt es also eine Obergrenze. Ist das alles was gesagt werden kann? Wo in der Literatur wurde dies untersucht?

Martin Berger

@NicholasMancuso Die Beispiele, die ich gebe, sind gleichmäßige Verteilungen. Aber man kann die gleiche Frage über ungleichmäßige Verteilungen stellen. Man kann sich auch über Verteilungen auf

wundern . In Bezug auf diskrete Verteilungen: Auf den ersten Blick scheint das Zählen im Allgemeinen nicht ausreichend zu sein. Sie müssen auch in der Lage sein, das

te Element zu generieren , nachdem Sie

einheitlich ausgewählt haben . Das heißt, es könnte der Fall sein, dass das Zählen der Kern des Problems ist.

R

$\mathbb{R}$

i

$i$

i

$i$

Martin Berger

@ NikosM. Vielen Dank, aber auch dieser Link sagt nichts über die Komplexität der zugrunde liegenden Distribution aus. Die Referenz spricht von einer Transformation

der Gleichverteilung. Diese Transformation kann jedoch rechnerisch schwierig oder einfach sein.

ϕ

$\phi$

Martin Berger

Die Komplexität von Wahrscheinlichkeitsverteilungen zeigt sich insbesondere bei der Untersuchung von Verteilungsproblemen wie DistNP in Levins Theorie von durchschnittlichen .

Eine Verteilung ist P-berechenbar, wenn ihre kumulative Dichtefunktion in Polynomzeit ausgewertet werden kann.

Eine Verteilung ist P-abtastbar wenn wir sie in Polynomzeit können.

Wenn eine Verteilung P-berechenbar ist, ist sie P-sampierbar. Das Gegenteil ist nicht der Fall, wenn bestimmte Einwegfunktionen vorhanden sind.

Sie können die Definitionen auf andere Komplexitätsklassen erweitern.

Oded Goldreich hat eine nette Einführung zu dem Thema, das Sie vielleicht überprüfen möchten.

Kaveh
quelle

Danke, ich denke, eine Theorie von

abtastbaren Verteilungen ist so etwas wie das, wonach ich gesucht habe. Es gibt jedoch keinen Grund, die Aufmerksamkeit auf

zu beschränken . Sie können

abtastbare Verteilungen für jede Komplexitätsklasse

P

$P$

P

$P$

C

$C$

C

$C$ . Mit dem jüngsten Aufstieg probabilistischer Programmiersprachen wird dies immer wichtiger.

Martin Berger

@ Martin, ja. Dort war NIPS 2015 ein Tutorial zur probabilistischen Programmierung ( Folien , das Video wird ebenfalls veröffentlicht). Ich hörte, dass die Teilnehmer es sehr interessant fanden. Schön zu sehen, dass Leute an der Kreuzung von ML / Stats und PL arbeiten. :)

Kaveh

Ja, und das Hauptproblem ist, dass solche Sprachen (= generische, programmierbare Sampler) langsam sind. Wie können wir sie beschleunigen?

Martin Berger

Wahrscheinlichkeitsverteilungen und Rechenkomplexität

Antworten: