Właściwości wyrażalne w 2-CNF lub 2-SAT

Jak wykazać, że pewna właściwość nie może być wyrażona w 2-CNF (2-SAT)? Czy są jakieś gry, takie jak gry z kamieniami? Wygląda na to, że klasyczna gra w czarne kamyki i gra w czarno-białe kamyki są do tego nieodpowiednie (są one kompletne w PSPACE, według Hertela i Pitassi, SIAM J z Computing, 2010).

Lub jakieś techniki inne niż gry?

Edycja : Myślałem o właściwościach, które obejmują zliczanie (lub liczność) nieznanego predykatu ( predykat SO , jak powiedzieliby teoretycy modeli skończonych). Na przykład, jak w przypadku Kliki lub nieważonego dopasowywania. (a) Klika : Czy na danym wykresie występuje klika taka, że podany jest numer ? (b) Dopasowanie : Czy istnieje pasujące w takie jak ? $C$ $G$ $|C| \ge$ $K$ $~$ $M$ $G$ $|M| \ge K$

Czy 2-SAT może się liczyć? Czy ma mechanizm zliczania? Wydaje się wątpliwe.

sat lower-bounds combinatorial-game-theory Sameer Gupta
źródło

Rozumiem, że w teorii modeli skończonych istnieją gry Ehrenfeucht – Fraïssé (dla FO) i gry Ajtai-Fagin (dla monadycznego SO). Ale nie jestem pewien, czy są one wystarczające tutaj. Również gry w FMT komplikują się w uporządkowanych strukturach, prawda?

Sameer Gupta,

@Marzio wydaje się to jakimś dowodem na to, że nie wszystkie funkcje boolowskie są wyrażalne w 2CNF, ponieważ, jak twierdzisz, odpowiedź na pytanie (nie jestem tego pewna, nie widzę tego jako oczywistego). co to za dowód? czy jest gdzieś opublikowany?

vzn

@vzn: trywialna funkcja boolowska, której nie można wyrazić w 2-CNF to:

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

$(x_1 \lor x_2 \lor x_3)$

Marzio De Biasi

@SameerGupta: po przeformułowaniu perhpas pytanie staje się trudne :-); rzeczywiście , gdzie jest ograniczony do klauzul z dwiema zmiennymi (SO-Krom) przechwytuje NL nad uporządkowanymi strukturami, podczas gdy egzystencjalne SO przechwytuje NP. Oczywiście ograniczone do FO 2-SAT nie mogą się liczyć (a gra Ehrenfeucht – Fraïssé lub techniki kompaktowości są wystarczająco daleko, ponieważ można ich użyć, aby udowodnić, że PARYSTYWA nie można zdefiniować FO).

\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

dobrze. wydaje się, że istnieje jakaś ogólna teoria, że SAT nie może wyrazić wszystkich funkcji boolowskich dla stałej . co to za teoria? to pytanie dotyczy specjalnego przypadku . zauważ, że istnieje koncepcja „redukcji” -SAT do 3-SAT przez transformację Tseitin . widziałem także podobną koncepcję w dowodach w dolnych granicach obwodu monotonicznego (Razborov).

k

$k$

k

$k$

k = 2

$k=2$

n

$n$

vzn

Odpowiedzi:

Rodzina bitwektorów to klasa rozwiązań problemu 2-SAT wtedy i tylko wtedy, gdy ma właściwość mediany: jeśli zastosujesz funkcję większości bitowej do trzech dowolnych rozwiązań, otrzymasz inne rozwiązanie. Patrz np. Https://en.wikipedia.org/wiki/Median_graph#2-satisfiable i jego odniesienia. Jeśli więc znajdziesz trzy rozwiązania, dla których nie jest to prawdą, to wiesz, że nie można tego wyrazić w 2-CNF.

David Eppstein
źródło

David, dzięki, sprawdzi to. @vzn - Czy odpowiedź Davida jest związana z tym, co skomentowałeś 2 dni temu na stronie czatu, że formuły 3SAT istnieją dla wszystkich zestawów wektorów bitowych i szukasz wyniku dla formuł 2SAT dotyczących zestawów wektorów bitowych?

Sameer Gupta

David, Yuval - Z pewnością twoje dowody będą działać, jeśli użyjesz tego samego zestawu zmiennych. Ale co, jeśli zestaw używanych zmiennych może być zupełnie inny? Spójrz na odpowiedź Martina Seymour'a tutaj: cstheory.stackexchange.com/questions/200/… - Aby pokazać, że nie ma zadowalającej redukcji (najlepiej logspace) z K-Clique lub K-Matching do 2SAT wymagałoby innego dowodu . Myśli?

Sameer Gupta

Dodanie zmiennych pomocniczych, a następnie ich rzutowanie nie pomoże, ponieważ jeśli właściwość mediany jest prawdziwa dla rozszerzonego systemu zmiennych, to nadal jest prawdziwa w projekcji.

David Eppstein

Innym sposobem na stwierdzenie, że mediana (lub większość) jest polimorfizmem dla ograniczeń 2SAT. W rzeczywistości wiadomo, że każdy CSP (nawet nie-boolowski), który ma większość jako polimorfizm, znajduje się w

(Dalmau-Krokhin '08).

N L \subseteq P

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

arnab

Niech będzie właściwością zmiennych. Załóżmy, że istnieje wzór 2CNF taki, że $P(x_1,\ldots,x_n)$ $n$ $\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ Twierdzimy, że jest równoważne formule 2CNF obejmującej tylko . Aby to udowodnić, wystarczy pokazać, jak wyeliminować . Napisz

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$

gdzie

są literałami, a

nie obejmuje

. Wzór

jest równoważny

φ = χ \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$

Dowodzi to twierdzenia, gdy

nie występuje w klauzuli jednostki; jeśli tak, możemy to wyeliminować bezpośrednio.

χ \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
źródło

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$

(Tak, znam te funkcje obliczeniowe dodawania, mnożenia i liczenia, ale łatwo przekonwertować je na wersje decyzyjne ich problemów).

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

(c) Tak więc do zliczania , nawet jeśli możesz nie być w stanie uzyskać równoważnego wyrażenia w 2-CNF, stosując metodę opisaną w (b), możesz uzyskać równoważne wyrażenie 2-CNF.

Więc tak, 2-SAT może liczyć.

$NL$ $|M|$ $NL$

Martin Seymour
źródło

Re (c), jeśli wierzysz mojej odpowiedzi, wówczas równoważną ekspresję 2-CNF można przekształcić w bona fide równoważną ekspresję 2-CNF.

Yuval Filmus,

-

$-$

$~$

Możesz przeczytać moją odpowiedź i przekonać się sam. Zauważ, że w tym przypadku nie ma ograniczeń czasu / przestrzeni.

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$

$~$