Tugas untuk membuat formula tidak memuaskan

8

Mari kita bayangkan kita memiliki rumus memuaskan Masalah yang harus dipecahkan adalah "Apakah ada tugas untuk variabel yang akan membuat F tidak memuaskan? " Salah satu cara penyelesaiannya adalah dengan menemukan semua solusi untuk F dalam hal variabel dan jika hitungnya < , solusi yang hilang akan menjadi jawabannya, tetapi kompleksitas dari algoritma ini sangat besar, jika jumlah penugasan tersebut kecil. $F(A_0, A_1,...A_k,S_0,...,S_n)$ $(S_0,...,S_n)$ $S_0,...,S_n$ $2^n$

Pertanyaan saya adalah:

Apakah ada cara untuk menyelesaikan masalah dengan lebih sedikit panggilan pemecah SAT?
Apakah itu masalah teori yang terkenal (Apa yang harus saya baca di google tentang hal itu)?

logic satisfiability sat-solvers Grigor Aghanyan
sumber

1

"Yang akan membuat F tidak memuaskan" - itu tidak masuk akal. Apakah maksud Anda "tidak memuaskan F"? Kemudian Anda berbicara tentang masalah TAUTOLOGY (resp. Melengkapi itu).

Raphael

Mengabaikan fakta bahwa pertanyaan itu tidak masuk akal, saya pikir mencoba mencari solusi untuk mungkin apa yang Anda cari.

\neg F (A_{0}, A_{1}, \dots, A_{k}, S_{0}, \dots, S_{n})

$\neg F(A_0,A_1,\ldots, A_k,S_0,\ldots, S_n)$

Dave Clarke

Mungkin saya tidak jelas. Setelah menerapkan penugasan untuk kami akan memiliki rumus dan ini harus tidak memuaskan.

(S_{0}, . . ., S_{n})

$(S_0,...,S_n)$

G (A_{0}, . . ., A_{k})

$G(A_0 ,..., A_k)$

Grigor Aghanyan

6

Masalah Anda adalah kanonik $\Sigma_2^P$ masalah -lengkap:

\exists \vec{S} \forall \vec{SEBUAH} \neg F (\vec{SEBUAH}, \vec{S}) .

$\exists \vec{S} \forall \vec{A} \lnot F(\vec{A},\vec{S}).$ Dengan demikian, itu dianggap lebih sulit daripada SAT (yang

Σ_{1}^{P}

$\Sigma_1^P$ ). Memecahkannya dengan beberapa panggilan SAT-oracle mirip dengan menyelesaikan SAT itu sendiri secara efisien (pertanyaan P vs NP), meskipun bisa jadi itu

Σ_{2}^{P} = Σ_{1}^{P}

$\Sigma_2^P = \Sigma_1^P$ sementara

P \neq N P

$P \neq NP$ , jadi dalam beberapa hal ada lebih banyak harapan untuk masalah Anda daripada untuk SAT itu sendiri.

Yuval Filmus
sumber

Persis. Terima kasih atas jawabannya. Jadi solusinya dengan

2^{n}

$2^n$ pemecah panggilan adalah "bukan solusi yang buruk" untuk itu? Beberapa tautan untuk makalah tentang masalah ini akan banyak membantu saya.

Grigor Aghanyan

Secara praktis mungkin ada heuristik yang berfungsi dengan baik untuk beberapa masalah, tapi saya tidak menyadarinya. Hirarki polinomial (yang berisi

Σ_{2}^{P}

$\Sigma_2^P$ ) harus dicakup dalam buku teks tentang kompleksitas komputasi.

Yuval Filmus

4

Ini adalah masalah yang terkenal: ini adalah masalah 2QBF. Sayangnya, ini jauh lebih sulit daripada SAT. Ada pemecah QBF yang tersedia. Anda dapat mencoba menemukan pemecah QBF (atau, bahkan lebih baik lagi, pemecah 2QBF) dan melihat apakah pemecah itu bisa menyelesaikan formula Anda. Namun, pemecah QBF tidak berskala serta pemecah SAT; QBF secara signifikan lebih sulit daripada SAT.

Lihat https://cstheory.stackexchange.com/q/11022/5038 dan http://www.qbflib.org/ untuk beberapa sumber yang mungkin bisa membantu.

DW
sumber

Tugas untuk membuat formula tidak memuaskan

Jawaban: