Apa bukti spesifik yang ada untuk P = RP?

RP adalah kelas masalah yang dapat diputuskan oleh mesin Turing nondeterministik yang berakhir dalam waktu polinomial, tetapi itu juga memungkinkan kesalahan satu sisi. P adalah kelas masalah yang biasa diputuskan oleh mesin Turing deterministik yang berakhir dalam waktu polinomial.

P = RP mengikuti dari hubungan dalam kompleksitas sirkuit. Impagliazzo dan Wigderson menunjukkan bahwa P = BPP mengikuti jika beberapa masalah yang dapat diputuskan dalam waktu eksponensial deterministik juga memerlukan sirkuit ukuran eksponensial (perhatikan bahwa P = BPP menyiratkan P = RP). Mungkin karena hasil ini, tampaknya ada perasaan di antara beberapa teori kompleksitas bahwa pengurangan probabilistik mungkin dapat derandomisasi.

Apa bukti spesifik lain yang ada bahwa P = RP?

Adanya masalah dalam DTIME (2 ^ O (n)) yang membutuhkan sirkuit ukuran eksponensial untuk menghitung (yang merupakan asumsi dalam IW) tampaknya masuk akal karena jika tidak kita akan memiliki ketidakseragaman memberikan percepatan pada SETIAP masalah komputasi - yang sepenuhnya bertentangan dengan pemikiran saat ini yang tidak melihat kesenjangan "terlalu signifikan" antara kompleksitas seragam dan tidak seragam untuk masalah "normal". Pemikiran ini berasal dari kenyataan bahwa ada sangat sedikit contoh di mana algoritma "tidak seragam" diketahui yang secara signifikan lebih baik daripada yang seragam yang dikenal (sekali lagi kecuali untuk derandomisasi).

Sepotong "bukti" lain adalah bahwa relatif terhadap nubuat acak kita memiliki P = BPP.

Setiap hasil derandomisasi konkret memberikan bukti bahwa P = BPP. Karena PRIMES dalam P (Agrawal-Kayal-Saxena'02) adalah salah satu contoh yang baik. Secara umum, ada beberapa masalah alami dalam BPP yang tidak diketahui dalam P (Polynomial Identity Testing adalah satu pengecualian penting.)

Serupa dengan semangat pada hasil yang Anda sebutkan, Hastad-Impagliazzo-Levin-Luby '99 menunjukkan bahwa keberadaan fungsi satu arah menyiratkan keberadaan generator pseudorandom. Meskipun ini tidak secara langsung menyiratkan P = BPP berdasarkan pada keberadaan fungsi satu arah, itu menunjukkan bahwa generator pseudorandom mengikuti dari asumsi kriptografi minimal. Ini dapat dilihat sebagai petunjuk lain bahwa BPP tidak lebih kuat dari P.

Penting untuk dicatat bahwa mengatakan "pengurangan probabilistik dapat [mungkin] diderandomisasi" jauh lebih kuat daripada P = RP. Faktanya, satu formalisasi dari gagasan derandomisasi semua pengurangan acak adalah bahwa relatif terhadap setiap oracle , yang kita tahu salah (misal Heller. Relativized hierarki polinomial yang memperpanjang dua level, Teori Sistem Matematika 17 (2) ): 71-84, 1984 memberikan oracle di mana yang tidak sama dengan oleh Teorema Hierarki Waktu).X Z P P = R P = E X P $P^X=RP^X$ $X$$ZPP=RP=EXP$$P$

Di atas, tentu saja, berbicara tentang derandomisasi pengurangan Turing polinomial-waktu secara acak, daripada pengurangan banyak-satu polinomial-waktu biasa. Saya tidak akan terkejut jika oracle Heller dapat diadaptasi untuk memberikan satu set X sehingga untuk semua Y, Y adalah eksponensial-waktu banyak orang direduksi menjadi X jika Y adalah RP-dapat direduksi menjadi X, tetapi tanpa melalui konstruksi saya tidak bisa bersumpah untuk itu.

Valiant dan Vazirani menunjukkan pada tahun 1986 bahwa ada pengurangan secara acak SAT menjadi , yang merupakan masalah keputusan berdasarkan SAT di mana hanya perbedaan antara instance yang memuaskan dan tidak memuaskan yang penting. Jika adalah predikat salah, maka adalah masalah memutuskan apakah ada satu solusi. Q = ⊥ U S A T $USAT_Q$$Q = \bot$$USAT_{\bot}$

Solusi untuk rumus Boolean adalah (0,1) -vektor yang menetapkan nilai kebenaran ke variabel bebas di , sehingga terpenuhi. Solusi terisolasi to adalah solusi, dengan properti tambahan yang berbeda dari solusi lain lebih dari nilai . (Secara bergantian, adalah solusi terisolasi jika jarak Hamming ke solusi lain melebihi .)ϕ ϕ k x ϕ k x k x $\phi$$\phi$$\phi$$k$$x$$\phi$$k$$x$$k$$x$$k$

Biarkan -ISOLASI SAT menjadi masalah yang mengharuskan memutuskan apakah rumus input CNF memiliki solusi yang terisolasi. Jika menunjukkan jumlah variabel dalam sebuah instance, maka dan -ISOLATED SAT adalah masalah yang sama persis.$k$n U S A T ⊥$k$$n$$USAT_{\bot}$$n$

Untuk setiap , dengan menduplikasi setiap variabel berkali-kali secara polinomial, reduksi deterministik dapat dilakukan dari SAT ke SAT -isolated SAT. (Detail tersedia di sini .) Ini tampaknya memberikan bukti lebih lanjut bahwa kesenjangan antara reduksi deterministik dan acak adalah "kecil".n 1 - $\epsilon > 0$$n^{1-\epsilon}$