Pengambilan sampel formula 3-SAT yang memuaskan

Pertimbangkan tugas komputasi berikut: Kami ingin mengambil sampel rumus 3-SAT dari variabel (varian: variabel klausa) berkenaan dengan distribusi probabilitas seragam, dikondisikan pada rumus yang memuaskan: $n$ $n$ $m$

T1: Dapatkah ini dicapai secara efisien oleh komputer klasik (dengan bit acak)?

T2: Bisakah ini dicapai secara efisien oleh komputer kuantum?

Saya juga tertarik pada dua varian berikut:

V2: Anda mencicipi semua formula dengan distribusi probabilitas yang memberikan formula yang memuaskan dua kali berat formula yang tidak memuaskan.

V3: Anda sampel di mana beratnya adalah jumlah tugas yang memuaskan (Di sini kami hanya peduli tentang Q2).

Pembaruan: Jawaban Colins menunjukkan algoritma sederhana untuk V3. (Saya salah berasumsi bahwa ini sulit secara klasik.) Izinkan saya menyebutkan varian lain dari ketiga pertanyaan ini:

Anda menentukan klausa di muka dan Anda perlu sampel himpunan bagian acak memuaskan dari klausa input. $m$

cc.complexity-theory quantum-computing sample-complexity Gil Kalai
sumber

Pertanyaan yang sangat menarik. Saya akan terkejut jika ada algoritma yang dikenal untuk melakukan tugas-tugas ini secara efisien.

Giorgio Camerani

Jawaban:

Ada algoritma sederhana untuk V3. Saya akan menggunakan konvensi bahwa ada kemungkinan klausa, jadi rumus. (Ini hanya untuk kesederhanaan - jika Anda tidak ingin semua klausa dianggap valid, itu tidak akan memengaruhi argumen berikut.) $(2n)^3$ $2^{8n^3}$ $8n^3$

Pilih tugas acak dari $\{0,1\}^n$ $7n^3$ $1/2$ $\phi$ $m$ $m$ $7n^3$

Colin McQuillan
sumber

Ini disebutkan dalam intro untuk Menghasilkan instance masalah yang memuaskan , oleh D Achlioptas, C Gomes, H Kautz, B Selman.

Colin McQuillan