Distribusi Probabilitas dan Kompleksitas Komputasi

Pertanyaan ini adalah tentang persimpangan teori probabilitas dan kompleksitas komputasi. Satu pengamatan utama adalah bahwa beberapa distribusi lebih mudah dihasilkan daripada yang lain. Misalnya masalah

Dengan diberi nomor $n$ , kembalikan nomor terdistribusi secara seragam dengan . $i$ $0 \leq i < n$

mudah dipecahkan. Di sisi lain, masalah berikut ini atau tampaknya jauh lebih sulit.

Diberi nomor , kembalikan angka sedemikian rupa sehingga adalah (angka Gödel) bukti valid panjang n dalam aritmatika Peano. Selain itu, jika jumlah bukti tersebut adalah , maka probabilitas untuk mendapatkan bukti spesifik panjang harus . $n$ $i$ $i$ $pr(n)$ $n$ $\frac{1}{pr(n)}$

Ini menunjukkan kepada saya bahwa distribusi probabilitas datang dengan gagasan tentang kompleksitas komputasi. Selain itu, kompleksitas ini mungkin terkait erat dengan masalah keputusan yang mendasarinya (apakah sub-rekursif, misalnya , , rekursif, berulang secara berulang, atau lebih buruk). $P$ $EXP$

Pertanyaan saya adalah: bagaimana seseorang mendefinisikan kompleksitas komputasi dari distribusi probabilitas, terutama di mana masalah keputusan yang mendasarinya tidak dapat ditentukan. Saya yakin ini sudah diselidiki, tetapi saya tidak yakin ke mana harus mencari.

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

Contoh lain yang menarik (tetapi yang dapat ditentukan) adalah transformasi quantum fourier. Diberikan mengembalikan angka sehingga probabilitas sebanding dengan, .

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

Logika Pengembaraan

Kedua contoh Anda adalah distribusi seragam diskrit. Saya akan membayangkan kompleksitas yang berbeda dalam betapa sulitnya menghitungdi mana adalah dukungan.

| χ |

$|\chi|$

χ

$\chi$

Nicholas Mancuso

@NicholasMancuso Saya setuju bahwa penghitungan + pilihan yang tidak sesuai selalu dapat digunakan. Jadi dalam arti tertentu ia memberi batas atas. Apakah ini semua yang bisa dikatakan? Di mana dalam literatur ini telah diselidiki?

Martin Berger

@NicholasMancuso Contoh yang saya berikan adalah distribusi seragam. Tetapi orang dapat mengajukan pertanyaan yang sama tentang distribusi yang tidak seragam. Anda juga dapat bertanya-tanya tentang distribusi di . Sebagai salam distribusi diskrit: prima facie, penghitungan tampaknya tidak cukup pada umumnya, Anda juga harus mampu untuk menghasilkan elemen th, setelah Anda seragam memilih . Yang mengatakan, itu mungkin menjadi kasus bahwa penghitungan adalah inti dari masalah.

R

$\mathbb{R}$

i

$i$

i

$i$

Martin Berger

@NikosM. Terima kasih, tetapi tautan itu juga tidak mengatakan apa pun tentang kompleksitas distribusi yang mendasarinya. Referensi berbicara tentang transformasi pada distribusi seragam. Tetapi transformasi itu mungkin sulit / atau mudah secara komputasi.

ϕ

$\phi$

Martin Berger

Kompleksitas distribusi probabilitas muncul terutama dalam studi masalah distribusi seperti DistNP dalam teori Levin tentang teori kompleksitas kasus rata - rata .

Distribusi adalah P-computable jika fungsi kepadatan kumulatifnya dapat dievaluasi dalam waktu polinomial.

Distribusi adalah P-samplable jika kita dapat sampel dari mereka dalam waktu polinomial.

Jika distribusi adalah P-computable maka P-sampable. Kebalikannya tidak benar jika ada fungsi satu arah tertentu.

Anda dapat memperluas definisi ke kelas kompleksitas lainnya.

Oded Goldreich memiliki catatan pengantar yang bagus tentang topik yang mungkin ingin Anda periksa.

Kaveh
sumber

Terima kasih, saya pikir teori distribusi -

sederhana adalah sesuatu seperti yang saya cari. Tetapi tidak ada alasan untuk membatasi perhatian

, Anda dapat menentukan

distribusi -samplable untuk setiap kelas kompleksitas

. Dengan munculnya bahasa pemrograman probabilistik yang menjadi penting.

P

$P$

P

$P$

C

$C$

C

$C$

Martin Berger

@ Martin, ya. Ada tutorial tentang Pemrograman Probabilistik ( slide , video akan diposting juga) di NIPS 2015. Saya mendengar orang-orang yang hadir merasa sangat menarik. Senang melihat orang yang bekerja di persimpangan ML / Stats dan PL. :)

Kaveh

Ya, dan masalah utamanya adalah bahasa-bahasa seperti itu (= generik, sampler yang dapat diprogram) lambat. Bagaimana kita bisa mempercepatnya?

Martin Berger

Distribusi Probabilitas dan Kompleksitas Komputasi

Jawaban: