Properti dapat diekspresikan dalam 2-CNF atau 2-SAT

Bagaimana seseorang menunjukkan bahwa properti tertentu tidak dapat dinyatakan dalam 2-CNF (2-SAT)? Apakah ada game, seperti game kerikil? Tampaknya game kerikil hitam klasik dan game kerikil hitam-putih tidak cocok untuk ini (mereka PSPACE lengkap, menurut Hertel dan Pitassi, SIAM J of Computing, 2010).

Atau teknik apa pun selain permainan?

Sunting : Saya sedang memikirkan properti yang melibatkan penghitungan (atau kardinalitas) dari predikat yang tidak diketahui ( predikat SO , seperti yang dikatakan oleh para ahli teori model hingga). Misalnya, seperti dalam Klik atau Pencocokan tak tertimbang. (a) Klik : Apakah ada klik pada grafik yang diberikan sehingga beberapa angka ? (B) Matching : Apakah ada cocok di sehingga ? $C$ $G$ $|C| \ge$ $K$ $~$ $M$ $G$ $|M| \ge K$

Bisakah 2-SAT dihitung? Apakah ada mekanisme penghitungan? Sepertinya ragu.

sat lower-bounds combinatorial-game-theory Sameer Gupta
sumber

Saya mengerti bahwa ada game Ehrenfeucht – Fraïssé (untuk FO) dan game Ajtai-Fagin (untuk SO monadik) dalam teori model hingga. Tetapi tidak yakin apakah mereka cukup di sini. Juga game di FMT jadi rumit dengan struktur yang dipesan, kan?

Sameer Gupta

@ Marszio sepertinya beberapa bukti bahwa tidak semua fungsi Boolean dapat diekspresikan dalam 2CNF karena Anda menyatakan akan menjawab pertanyaan (tidak benar-benar yakin akan hal itu, jangan melihatnya dengan jelas). bukti apa itu? apakah itu diterbitkan di suatu tempat?

vzn

@vzn: fungsi boolean sepele yang tidak dapat diekspresikan dalam 2-CNF adalah:

(x_{1} \lor x_{2} \lor x_{3})

$(x_1 \lor x_2 \lor x_3)$

Marzio De Biasi

@SameerGupta: setelah reformulasi, perhpas pertanyaannya menjadi sulit :-); memang

, di mana

terbatas pada klausa dengan dua variabel (SO-Krom) menangkap NL lebih memerintahkan struktur, sementara menangkap eksistensial SO NP. Jelas terbatas pada FO 2-SAT tidak dapat dihitung (dan permainan Ehrenfeucht – Fraïssé atau teknik kekompakan cukup jauh, karena Anda dapat menggunakannya untuk membuktikan bahwa PARITY bukan FO yang dapat didefinisikan).

\exists P_{1} . . . \exists P_{n} \forall \bar{z} φ (P_{1}, . . ., P_{n}, \bar{z})

$\exists P_1...\exists P_n \forall \bar{z} \varphi( P_1,...,P_n, \bar{z})$

φ

$\varphi$

Marzio De Biasi

baik. tampaknya ada beberapa teori umum bahwa

-SAT tidak dapat mengekspresikan semua fungsi boolean untuk konstanta

. teori apa itu? pertanyaan ini menanyakan tentang kasus khusus

. perhatikan ada konsep "pengurangan"

-SAT menjadi 3-SAT melalui transformasi Tseitin . juga telah melihat konsep serupa muncul di sirkuit monoton bukti batas bawah (Razborov).

k

$k$

k

$k$

k = 2

$k=2$

n

$n$

vzn

Jawaban:

Keluarga bitvectors adalah kelas solusi untuk masalah 2-SAT jika dan hanya jika ia memiliki properti median: jika Anda menerapkan fungsi mayoritas bitwise ke tiga solusi Anda mendapatkan solusi lain. Lihat misalnya https://en.wikipedia.org/wiki/Median_graph#2-satisfiability dan rujukannya. Jadi jika Anda dapat menemukan tiga solusi yang ini tidak benar, maka Anda tahu itu tidak dapat dinyatakan dalam 2-CNF.

David Eppstein
sumber

David, terima kasih, akan mencari ini. @vzn - Apakah jawaban David terkait dengan apa yang Anda komentari 2 hari lalu di situs obrolan, bahwa rumus 3SAT ada untuk semua set vektor bit, dan mencari hasil untuk rumus 2SAT tentang set bit-vektor?

Sameer Gupta

David, Yuval - Tentu saja bukti Anda akan berfungsi jika seseorang menggunakan set variabel yang sama. Tetapi bagaimana jika set variabel yang digunakan bisa sangat berbeda? Lihatlah jawaban Martin Seymour di sini: cstheory.stackexchange.com/questions/200/… - Untuk menunjukkan bahwa tidak ada pengurangan yang memuaskan (lebih disukai logspace) dari K-Clique atau K-Matching ke 2SAT akan membutuhkan bukti yang berbeda . Pikiran?

Sameer Gupta

Menambahkan variabel bantu dan kemudian memproyeksikannya tidak akan membantu, karena jika properti median benar untuk sistem variabel yang diperbesar maka itu masih benar dalam proyeksi.

David Eppstein

Cara lain untuk mengatakannya adalah median (atau mayoritas) adalah polimorfisme untuk kendala 2SAT. Bahkan, diketahui bahwa setiap CSP (bahkan non-boolean) yang memiliki mayoritas sebagai polimorfisme adalah di

(Dalmau-Krokhin '08).

N L \subseteq P

$\mathsf{NL} \subseteq \mathsf{P}$

arnab

Biarkan menjadi properti pada variabel. Misalkan ada rumus 2CNF sedemikian sehingga $P(x_1,\ldots,x_n)$ $n$ $\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ Kami mengklaim bahwa setara dengan rumus 2CNF yang hanya melibatkan . Untuk membuktikan ini, cukup dengan menunjukkan bagaimana cara menghilangkan . Tulis

P (x_{1}, \dots, x_{n}) \Leftrightarrow \exists y_{1} \dots \exists y_{m} φ (x_{1}, \dots, x_{n}, y_{1}, \dots, y_{m}) .

$P(x_1,\ldots,x_n) \Leftrightarrow \exists y_1 \cdots \exists y_m \varphi(x_1,\ldots,x_n,y_1,\ldots,y_m).$

φ

$\varphi$

ψ

$\psi$

x_{1}, \dots, x_{n}

$x_1,\ldots,x_n$

y_{m}

$y_m$

mana

adalah literal, dan

tidak melibatkan

. Rumus

setara dengan

φ = χ \land ⋀_{k = 1}^{s} (y_{m} \lor U_{k}) \land ⋀_{ℓ = 1}^{t} (\bar{y_{m}} \lor V_{ℓ}),

$\varphi = \chi \land \bigwedge_{k=1}^s (y_m \lor U_k) \land \bigwedge_{\ell=1}^t (\overline{y_m} \lor V_\ell),$

U_{k}, V_{ℓ}

$U_k,V_\ell$

χ

$\chi$

y_{m}

$y_m$

φ

$\varphi$

ini membuktikan klaim ketika

tidak muncul dalam unit klausa; jika ya, kita bisa menghilangkannya secara langsung.

χ \land (\bar{y_{m}} \Rightarrow ⋀_{k = 1}^{s} U_{k}) \land (y_{m} \Rightarrow ⋀_{ℓ = 1}^{t} V_{ℓ}) ⟺ χ \land (⋀_{k = 1}^{s} U_{k} \lor ⋀_{ℓ = 1}^{t} V_{ℓ}) ⟺ χ \land ⋀_{k = 1}^{s} ⋀_{ℓ = 1}^{t} (U_{k} \lor V_{ℓ})

$\chi \land (\overline{y_m} \Rightarrow \bigwedge_{k=1}^s U_k) \land (y_m \Rightarrow \bigwedge_{\ell=1}^t V_\ell) \\ \Longleftrightarrow \\ \chi \land (\bigwedge_{k=1}^s U_k \lor \bigwedge_{\ell=1}^t V_\ell) \\ \Longleftrightarrow \\ \chi \land \bigwedge_{k=1}^s \bigwedge_{\ell=1}^t (U_k \lor V_\ell)$

y_{m}

$y_m$

$P(x_1,\ldots,x_n)$ $\psi(x_1,\ldots,x_n)$ $P$ $P$ $K$ $K$ $n$

Yuval Filmus
sumber

y_{i}

$y_i$

ψ

$\psi$

x_{1}

$x_1$

x_{2}

$x_2$

\dots

$\cdots$

x_{n}

$x_n$

ϕ_{1}

$\phi_1$

ϕ_{2}

$\phi_2$

ϕ_{2}

$\phi_2$

y_{i}

$y_i$

y_{i}

$y_i$

$L$ $-$ $L$

(Ya, saya tahu penambahan, perkalian, dan penghitungan fungsi penghitungan, tetapi mudah untuk mengubahnya menjadi versi keputusan dari masalah mereka masing-masing.)

$L \subseteq NL$ $NL$ $AC^0$ $AC^0$

(c) Jadi untuk penghitungan , meskipun Anda mungkin tidak dapat memperoleh ekspresi setara dalam 2-CNF, menggunakan metode yang diuraikan dalam (b), Anda bisa mendapatkan ekspresi 2-CNF yang memuaskan .

Jadi ya, 2-SAT bisa dihitung.

$NL$ $|M|$ $NL$

Martin Seymour
sumber

Re (c), jika Anda yakin dengan jawaban saya maka ekspresi 2-CNF yang setara dapat dikonversi menjadi ekspresi 2-CNF setara yang bonafid.

Yuval Filmus

-

$-$

$~$

Anda dapat membaca jawaban saya dan melihat sendiri. Perhatikan bahwa tidak ada batasan waktu / ruang dalam kasus ini.

Yuval Filmus

L

$L$

{A C}^{0}

$\mathrm{AC}^0$

f

$f$

x \in L

$x\in L$

f (x)

$f(x)$

ϕ

$\phi$

x_{i}

$x_i$

ϕ

$\phi$

-

$-$

x_{i}

$x_i$

$~$