Derandomisasi Valiant-Vazirani?

29

The Valiant-Vazirani teorema mengatakan bahwa jika ada algoritma waktu polinomial (deterministik atau acak) untuk membedakan antara formula SAT yang memiliki tepat satu tugas memuaskan, dan formula unsatisfiable - maka NP = RP . Teorema ini dibuktikan dengan menunjukkan bahwa UNIQUE-SAT adalah NP -hard dalam pengurangan acak .

Tunduk pada dugaan derandomisasi yang masuk akal, Teorema dapat diperkuat untuk "solusi efisien untuk UNIQUE-SAT menyiratkan NP = P ".

Naluri pertama saya adalah berpikir bahwa secara tersirat ada pengurangan deterministik dari 3SAT menjadi UNIQUE-SAT, tetapi tidak jelas bagi saya bagaimana pengurangan khusus ini dapat diderandomisasi.

Pertanyaan saya adalah: apa yang diyakini atau diketahui tentang "pengurangan derandomisasi"? Apakah ini / haruskah mungkin? Bagaimana dengan VV?

Karena UNIQUE-SAT selesai untuk PromiseNP di bawah pengurangan acak, dapatkah kita menggunakan alat derandomisasi untuk menunjukkan bahwa "solusi waktu polinomial deterministik untuk UNIQUE-SAT menyiratkan bahwa PromiseNP = PromiseP ?

cc.complexity-theory reductions derandomization unique-solution Henry Yuen
sumber

4

Adapun paragraf terakhir, PromiseP = PromiseNP setara dengan P = NP.

Tsuyoshi Ito

31

Di bawah asumsi derandomisasi yang tepat (lihat Klivan-van Melkebeek ) Anda mendapatkan yang berikut: Ada polytime computable st untuk semua , $f(\phi)=(\psi_1,\ldots,\psi_k)$ $\phi$

$\phi$ $\psi_i$
$\phi$ $\psi_i$

$\phi$ $k=1$

Lance Fortnow
sumber

P = B P P

$P=BPP$

P = B P P

$P=BPP$

S A T

$SAT$

P = N P

$P=NP$

1

Tidak. Anda perlu asumsi yang lebih kuat daripada P = BPP untuk derandomisasi Valiant-Vazirani (sekali lagi saya merujuk Anda ke Klivan-van Melkebeek). Bahkan jika Anda melakukan derandomisasi Valiant-Vaizarni ini hanya memberikan hasil yang saya sebutkan di atas - Anda tidak akan mendapatkan P = NP kecuali Anda memiliki algoritma yang bisa menyelesaikan kepuasan dengan saksi unik.

Lance Fortnow

P^{\oplus P} = B P P^{\oplus P}

$P^{\oplus P}=BPP^{\oplus P}$

P = B P P

$P=BPP$

P^{\oplus P} = B P P^{\oplus P}

$P^{\oplus P}=BPP^{\oplus P}$

22

Hanya untuk referensi, saya menemukan makalah yang sangat menarik ini hari ini, yang memberikan bukti bahwa pengurangan deterministik tidak mungkin:

Dell, H., Kabanets, V., Watanabe, O., & van Melkebeek, D. (2012). Apakah Lemma Valiant-Vazirani Isolasi diperbaiki? ECCC TR11-151

Mereka berpendapat bahwa ini tidak mungkin kecuali NP terkandung dalam P / poly.

Henry Yuen
sumber

Derandomisasi Valiant-Vazirani?

Jawaban: