Свойства, выраженные в 2-CNF или 2-SAT

Как можно показать, что определенное свойство не может быть выражено в 2-CNF (2-SAT)? Существуют ли игры, такие как игры в гальку? Похоже, что классическая игра с черной галькой и игра с черной и белой галькой для этого не подходят (они завершены PSPACE, согласно Hertel и Pitassi, SIAM J of Computing, 2010).

Или какие-либо методы, кроме игр?

Изменить : я думал о свойствах, которые включают подсчет (или количество элементов) неизвестного предиката ( предикат SO , как сказали бы теоретики конечных моделей). Например, как в клике или невзвешенном сопоставлении. (a) Клика : есть ли клика в данном графе G такая, что | C | ≥ какой-то номер K ? (b) Соответствие : существует ли такое соответствие M в G , что | М | ≥ K ?$C$$G$$|C| \ge$$K$$~$$M$$G$$|M| \ge K$

Может ли 2-SAT рассчитывать? Есть ли у него счетный механизм? Кажется сомнительным.

Семейство битвекторов - это класс решений задачи 2-SAT, если и только если он обладает медианным свойством: если вы примените функцию побитового большинства к любым трем решениям, вы получите другое решение. Смотрите, например, https://en.wikipedia.org/wiki/Median_graph#2-satisfiability и его ссылки. Таким образом, если вы можете найти три решения, для которых это не так, то вы знаете, что это не может быть выражено в 2-CNF.

Пусть - свойство по n переменным. Предположим , что существует 2CNF формула φ ( х 1 , ... , х п , у 1 , ... , у т ) , такие , что Р ( х 1 , ... , х п ) ⇔ ∃ у 1 ⋯ ∃ у м ф ( х $P(x_1,\ldots,x_n)$$n$$\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ Мы утверждаем, что φ эквивалентна формуле 2CNF ψ, включающей только x 1 , … , x n . Чтобы доказать это, достаточно показать, как устранить y m . Напишите φ = χ ∧ s ⋀ k = 1 ( y m ∨ U k ) ∧ t ⋀ ℓ

$$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,\ldots,x_n$$y_m$ гдеUK,Vℓявляются литералами, иχне включаетум. Формулаφэквивалентна х∧( ¯ у м ⇒ с ⋀ к = 1 Uк)∧(ум⇒ т ⋀ л = 1 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_\ell$$\chi$$y_m$$\varphi$ Это доказывает утверждение, когда y m не фигурирует в предложении единицы; если это произойдет, мы можем устранить это напрямую. $$\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$

Мы пришли к выводу , что можно представить в виде формулы 2CNF тогда и только тогда существует формула 2CNF ψ ( х 1 , ... , х п ) эквивалентна P . Следовательно, свойство P выражается как 2CNF, если каждое фальсифицирующее присваивание форсируется не более чем двумя литералами. В частности, K -clique и K -matching не могут быть выражены как 2CNF (кроме углового случая n -clique).$P(x_1,\ldots,x_n)$$\psi(x_1,\ldots,x_n)$$P$$P$$K$$K$$n$

$L$ $-$$L$

(Да, я знаю, что сложение, умножение и подсчет вычисляют функции, но их легко преобразовать в версии решения соответствующих задач.)

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

(c) Таким образом, для подсчета , даже если вы не можете получить эквивалентное выражение в 2-CNF, используя метод, описанный в (b), вы можете получить равноудаленное выражение 2-CNF.

Так что да, 2-SAT может рассчитывать.

$NL$$|M|$$NL$