Apakah keacakan memberi kita sesuatu di dalam P?

Misalkan adalah kelas dari masalah keputusan yang memiliki algoritma acak kesalahan dua sisi terikat yang berjalan dalam waktu . $\mathsf{BPTIME}(f(n))$ $O(f(n))$

Apakah kita tahu ada masalah sedemikian sehingga tetapi ? Apakah ketidakberadaannya terbukti? $Q \in \mathsf{P}$ $Q \in \mathsf{BPTIME}(n^k)$ $Q \not \in \mathsf{DTIME}(n^k)$

Pertanyaan ini ditanyakan pada cs.SE di sini , tetapi tidak mendapatkan jawaban yang memuaskan.

cc.complexity-theory ds.algorithms randomized-algorithms derandomization aelguindy
sumber

(1) BPP (f (n)) biasanya dilambangkan sebagai BPTIME (f (n)). (2) Dalam pengaturan kompleksitas komputasi, saya percaya ini terbuka. (Banyak contoh diketahui dalam kompleksitas kueri dan pengaturan kompleksitas komunikasi.) (3) Jika tidak ada yang sudah terbukti, maka kita sudah tahu bahwa P = BPP.

Tsuyoshi Ito

Ngomong-ngomong, dalam pertanyaan di cs.stackexchange.com, Anda memiliki beberapa kesalahpahaman tentang hubungan antara BPTIME dan ZPTIME, dan itu mungkin menjadi bagian dari alasan Anda belum menerima jawaban yang memuaskan.

Tsuyoshi Ito

@TsuyoshiIto Terima kasih, saya tidak setuju bahwa jika kita membuktikan tidak adanya maka kita tahu

, saya membatasi pengaturan untuk masalah di

. Mungkin,

, sedangkan

P = B P P

$P=BPP$

P

$P$

B P T I M E (n^{k}) \cap P = D T I M E (n^{k})

$BPTIME(n^k) \cap P = DTIME(n^k)$

secara umum, apakah saya kehilangan sesuatu? Bisakah Anda juga menunjukkan kesalahpahaman saya tentang

dan

, mungkin saya benar-benar melewatkan jawaban yang memuaskan ..

B P T I M E (n^{k}) \neq D T I M E (n^{k})

$BPTIME(n^k) \neq DTIME(n^k)$

B P T I M E

$BPTIME$

Z P T I M E

$ZPTIME$

aelguindy

Pertanyaan Anda tidak mengatakan bahwa Anda membatasi masalah Q untuk berada di dalam P. Jika itu maksud Anda, harap edit pertanyaan itu.

Tsuyoshi Ito

Untuk mendekati median 1 dari ruang metrik terbatas dengan beberapa kueri untuk fungsi jarak, titik acak memberikan perkiraan 2-perkiraan dan aprox (2 + eps) dengan probabilitas baik. Tetapi tidak ada algoritma deterministik yang menanyakan fungsi jarak

kali dapat melakukan lebih baik daripada perkiraan-4. [ Chang 2013 ]

o (n^{2})

$o(n^2)$

Neal Young

Jawaban:

Contoh lain adalah memperkirakan volume polihedron dalam dimensi tinggi. Ada batas bawah tanpa syarat pada strategi deterministik untuk memperkirakan volume bahkan faktor eksponensial, tetapi ada FPRAS untuk masalah tersebut.

Pembaruan: makalah yang relevan adalah (tautan ke PDF ):

I. Barany dan Z. Furedi. Menghitung volume sulit, Diskrit dan Geometri Komputasi 2 (1987), 319-326.

Suresh Venkat
sumber

Bisakah Anda memberikan referensi untuk batas bawah tanpa syarat?

T ....

referensi ditambahkan.

Suresh Venkat

Masalah : Array terdiri dari 1s dan 0s. Temukan sehingga adalah 1. $A[1..2n]$ $n$ $n$ $i$ $A[i]$

Anda diizinkan untuk menanyakan 'Nomor mana yang ada dalam '? Setiap permintaan membutuhkan waktu yang konstan. $A[i]$

Solusi : Algoritma Acak: Pilih indeks acak dan periksa apakah adalah 1. Jumlah kueri yang diharapkan adalah 2, tetapi algoritma deterministik apa pun harus membuat setidaknya kueri. Oleh karena itu, batas atas acak secara ketat lebih baik daripada batas bawah deterministik dalam model ini. $i$ $A[i]$ $n$

Ini adalah contoh dari kompleksitas kueri yang dirujuk oleh Tsuyoshi dalam komentar.

Jagadish
sumber

Algoritma deterministik apa pun harus membuat setidaknya

query dalam kasus terburuk .

n

$n$

argentpepper

Apa yang Anda maksud dengan "saat ini kami tidak tahu bukti batas bawah non-sepele untuk masalah apa pun di NP (apalagi P)"?

Kristoffer Arnsfelt Hansen

Mungkin saya menggunakan kata 'non-sepele' sembarangan. Aku berarti 'Saat ini, kami tidak dapat membuktikan tanpa syarat batas bawah dari

untuk

untuk SAT atau masalah dalam NP'. Apakah itu benar?

Ω (n^{k})

$\Omega(n^k)$

k > 0

$k>0$

Jagadish

Yah, mungkin bukan untuk masalah "baik" seperti SAT; tetapi ingat kita memiliki batas yang lebih rendah untuk masalah lain dari teorema hierarki waktu. Dan pertanyaannya bukan tentang masalah "baik", tetapi tentang kelas kompleksitas.

Kristoffer Arnsfelt Hansen

Ah benar Saya berasumsi bahwa OP tertarik pada masalah alam. Saya sudah mengedit jawaban saya.

Jagadish

$n\times n$ $\epsilon$ .

Masalah ini memiliki algoritma acak yang berjalan dalam waktu $O(n\log^2(n)/\epsilon^2)$ , yang (terbukti) tidak ada algoritma deterministik dapat cocok dengan [ GK95 ].

Lihat juga Algoritma acak yang efisien dan sederhana di mana determinisme sulit .

Neal Young
sumber