Secara ringkas mewakili sekumpulan solusi dari instance SAT

Pertanyaan ini muncul dalam benak saya setelah membaca kontribusi András Salamon dan Colin McQuillan untuk pertanyaan saya sebelumnya. Menghitung solusi dari formula Monotone-2CNF .

EDIT 30 ^th Mar 2011
Ditambahkan pertanyaan n ° 2.

EDIT 29 ^th Oktober 2010
Pertanyaan diulang setelah András usulan untuk meresmikan melalui gagasan bagus representasi dari set solusi (Saya telah memodifikasi gagasan nya sedikit).

Biarkan menjadi rumus CNF umum dengan variabel. Biarkan menjadi set solusinya. Jelas,mungkin eksponensial dalam . Biarkann S | S | n R S $F$$n$$S$$|S|$$n$$R$menjadi representasi dari . dikatakan baik jika dan hanya jika semua fakta berikut ini benar:$S$$R$

1. $R$ memiliki ukuran polinomial dalam .$n$
2. $R$ memungkinkan untuk menghitung solusi dalam dengan penundaan polinomial.$S$
3. | S $R$ memungkinkan untuk menentukandalam waktu polinomial (yaitu tanpa menyebutkan semua solusi). $|S|$

Akan lebih bagus jika memungkinkan, dalam waktu polinomial, untuk membangun seperti itu untuk setiap formula.$R$

Pertanyaan:

1. Apakah ada yang pernah membuktikan bahwa ada keluarga formula yang seperti bagus representasi tidak bisa eksis?
2. Adakah yang mempelajari hubungan antara representasi dan simetri yang ditunjukkan oleh ? Secara intuitif, simetri seharusnya membantu merepresentasikan dengan kompak karena mereka menghindari representasi eksplisit dari subset solusi ketika sebenarnya bermuara pada satu solusi saja (yaitu dari setiap Anda dapat memulihkan setiap dengan menerapkan simetri yang tepat, sehingga setiap itu sendiri mewakili seluruh )F S S ′ ⊂ S S ′ s i ∈ S ′ s j ∈ S ′ s i ∈ S ′ S $S$$F$$S$$S' \subset S$$S'$$s_i \in S'$$s_j \in S'$$s_i \in S'$$S'$

Sebagaimana dinyatakan (revisi 3), pertanyaan itu memiliki jawaban sederhana: tidak.

Alasannya adalah bahwa bahkan untuk kelas representasi yang sangat terbatas yang diberikan oleh sirkuit Boolean dengan gerbang AND, OR, dan NOT, tidak ada batas bawah nontrivial yang diketahui. (Jelas sebuah sirkuit yang mewakili juga akan mewakili secara implisit, dan mudah untuk menyebutkan solusinya dengan mengubah input ke sirkuit.)$F$$S$

Untuk representasi yang lebih terbatas, seperti monoton atau sirkuit kedalaman konstan, batas bawah eksponensial diketahui. Ada juga batas bawah eksponensial untuk mewakili formula dalam bentuk CNF atau DNF, meskipun ini dapat dilihat sebagai kasus khusus dari sirkuit kedalaman konstan. Akhirnya, representasi BDD dapat dilihat sebagai bentuk kompak dari DNF, tetapi ada rumus yang BDD membutuhkan ukuran eksponensial untuk setiap pemesanan variabel.

Untuk membuat pertanyaan Anda lebih tepat, harap pertimbangkan jawaban @ Joshua secara mendetail, dan tolong jelaskan apa yang Anda maksud dengan "sepele untuk menyebutkan setiap solusi tunggal".

Untuk revisi 4, perhatikan pernyataan tentang ukuran BDD. Bagian dari apa yang tampaknya Anda tanyakan adalah: apakah ada representasi yang lebih kompak dari formula DNF daripada BDD? Biarkan "BDD memiliki ukuran superpolynomial" berarti "setiap BDD yang mewakili fungsi yang sama dengan , terlepas dari pengurutan variabel, memiliki ukuran superpolinomial", dan biarkan "representasi yang bagus" berarti "representasi yang memungkinkan solusi untuk dihitung dengan penundaan polinomial". Pertanyaan yang lebih spesifik ini kemudian menjadi:$B$$B$

apakah ada keluarga formula dan representasi yang bagus yang memiliki ukuran polinom sedangkan BDD-nya memiliki ukuran superpolinomial?

Apakah ini menangkap esensi dari apa yang Anda minta?

[Jawaban ini sebagai tanggapan terhadap versi sebelum Revisi 6 dari 29 Oktober 2010.]

Saya pikir pertanyaan lebih atau kurang berfungsi sekarang, tetapi ada masalah teknis yang tersisa. Yaitu, cara memformalkan "sepele untuk menyebutkan setiap solusi tunggal dengan hanya melihat struktur seperti itu." Formalisasi yang mungkin naif (tetapi satu-satunya yang dapat saya saat ini) adalah sebagai berikut: misalkan menunjukkan representasi dari set solusi dari . Saat ini saya tidak membatasi selain itu di mana adalah CNF pada variabel. Maka kita ingin ada suatu algoritma sehingga dan$R(\varphi)$$S(\varphi)$$\varphi$$R$$|R(\varphi)| \leq poly(n)$$\varphi$$n$$A$$A(R(\varphi)) = S(\varphi)$$A$pada input berjalan dalam waktu .$R(\varphi))$$poly(n, |S|)$

Di bawah formalisasi ini, satu-satunya kasus yang sulit adalah kasus di mana adalah super-polinomial tetapi sub-eksponensial. Kasus-kasus yang tersisa ditangani oleh representasi dan algoritma : jika , lalu biarkan . Jika lalu biarkan . hanya menghasilkan , dan hanya menghitung dengan brute force dari . Sejak dalam kasus terakhir, ini masih berjalan dalam waktu .$S$$R$$A$$|S| \leq poly(n)$$R(\varphi) = (0, S)$$|S| \geq 2^{\Omega(n)}$$R(\varphi) = (1, \varphi)$$A(0, S)$$S$$A(1, \varphi)$$S$$\varphi$$|S| = 2^{\Omega(n)}$$O(|S|)$

Namun, kasus-kasus sulit secara umum tidak mungkin dilakukan di bawah formalisasi ini. Jika dan ada, itu berarti bahwa kompleksitas Kolmogorov -time-bounded dari setiap dibatasi oleh , yang tidak masuk akal (karena hampir semua himpunan memiliki kompleksitas Kolmogorov -time maksimal maksimum , yaitu ). (Di sini adalah waktu menjalankan sebagai fungsi .)$R$$A$$p$$S$$poly(n)$$S$$p$$|S|$$p$$A$$|S|$

(Perhatikan bahwa jika kita juga mensyaratkan bahwa berjalan dalam waktu , maka jawaban atas pertanyaannya adalah tidak secara umum, dengan asumsi : jika memiliki solusi unik, maka akan menyelesaikan dan dijalankan dalam waktu .p o l y ( n , | φ | ) P ≠ P r o m i s e U P φ A ( R ( φ ) ) φ p o l y ( n $R$$poly(n, |\varphi|)$$P \neq PromiseUP$$\varphi$$A(R(\varphi))$$\varphi$$poly(n)$