Propriedades expressáveis em 2-CNF ou 2-SAT

Como alguém mostra que uma determinada propriedade não pode ser expressa em 2-CNF (2-SAT)? Existem jogos, como jogos de seixos? Parece que o clássico jogo de pedras negras e preto e branco é inadequado para isso (eles são completos para o PSPACE, de acordo com Hertel e Pitassi, SIAM J of Computing, 2010).

Ou alguma outra técnica além dos jogos?

Edit : Eu estava pensando em propriedades que envolvem a contagem (ou cardinalidade) de um predicado desconhecido ( predicado SO , como diriam os teóricos do modelo finito). Por exemplo, como em Clique ou Correspondência não ponderada. (a) Clique : Existe um clique no gráfico fornecido modo que algum número dado ? (b) Correspondência : Existe um correspondente em tal que ? $C$ $G$ $|C| \ge$ $K$ $~$ $M$ $G$ $|M| \ge K$

O 2-SAT pode contar? Possui um mecanismo de contagem? Parece duvidoso.

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

Entendo que existem os jogos Ehrenfeucht – Fraïssé (para FO) e Ajtai-Fagin (para SO monádico) na teoria dos modelos finitos. Mas não tenho certeza se eles são suficientes aqui. Também os jogos na FMT ficam complicados com estruturas ordenadas, certo?

Sameer Gupta 28/11

@Marzio, parece uma prova de que nem todas as funções booleanas são expressáveis no 2CNF, como você afirma que responderia à pergunta (não tenho certeza disso, não a vejo como óbvia). o que é essa prova? é publicado em algum lugar?

vzn

@vzn: uma função booleana trivial que não é expressável em 2-CNF é:

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

$(x_1 \lor x_2 \lor x_3)$

Marzio De Biasi

@SameerGupta: após a reformulação, perhpas a pergunta se torna difícil :-); de fato

, onde

está limitado a cláusulas com duas variáveis (SO-Krom) captura nl sobre estruturas ordenadas, enquanto captura SO existencial NP. Obviamente, limitado a FO 2-SAT não pode contar (e as técnicas de compactação ou jogo de Ehrenfeucht-Fraïssé são suficientes, porque você pode usá-las para provar que PARITY não é definível por 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

Está bem. parece haver alguma teoria geral de que

SAT não pode expressar todas as funções booleanas para a constante

. o que é essa teoria? esta pergunta pergunta sobre o caso especial

. note que existe um conceito de "redução" de

-SAT para 3-SAT através da transformação Tseitin . também viram um conceito semelhante aparecer nas provas de limites inferiores do circuito monótono (Razborov).

k

$k$

k

$k$

k = 2

$k=2$

n

$n$

vzn

Respostas:

Uma família de vetores de bits é a classe de soluções para um problema 2-SAT se, e somente se, tiver a propriedade mediana: se você aplicar a função de maioria bit a bit a quaisquer três soluções, obterá outra solução. Veja, por exemplo, https://en.wikipedia.org/wiki/Median_graph#2-satisfiability e suas referências. Portanto, se você puder encontrar três soluções para as quais isso não é verdade, sabe que não pode ser expresso em 2-CNF.

David Eppstein
fonte

David, obrigado, vai procurar isso. @vzn - A resposta de David está relacionada ao que você comentou 2 dias atrás no site de bate-papo, que as fórmulas 3SAT existem para todos os conjuntos de vetores de bits e estão procurando um resultado para as fórmulas 2SAT relativas aos conjuntos de vetores de bits?

Sameer Gupta 29/11

David, Yuval - Certamente suas provas funcionarão se alguém usar o mesmo conjunto de variáveis. Mas e se o conjunto de variáveis usadas puder ser completamente diferente? Dê uma olhada na resposta de Martin Seymour aqui: cstheory.stackexchange.com/questions/200/… - Para mostrar que não há redução equi-satisfatória (preferencialmente espaço de log) de K-Clique ou K-Matching para 2SAT exigiria uma prova diferente . Pensamentos?

Sameer Gupta

Adicionar variáveis auxiliares e depois projetá-las não ajudará, porque se a propriedade mediana for verdadeira para o sistema aumentado de variáveis, ela ainda será verdadeira na projeção.

precisa

Outra maneira de dizer é que a mediana (ou maioria) é um polimorfismo para as restrições 2SAT. Na verdade, sabe-se que qualquer CSP (ainda não booleano) que tem maioria como um polimorfismo está em

(Dalmau-Krokhin '08).

N L \subseteq P

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

Arnab

Seja uma propriedade em variáveis. Suponha-se que não existe uma fórmula 2CNF tal que $P(x_1,\ldots,x_n)$ $n$ $\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ Afirmamos que é equivalente a uma fórmula 2CNF envolvendo apenas . Para provar isso, basta mostrar como eliminar . Escreva

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$

onde

são literais e

não envolve

. A fórmula

é equivalente a

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

Isto prova a reivindicação quando

não é apresentado na cláusula de uma unidade; se isso acontecer, podemos eliminá-lo diretamente.

χ \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
fonte

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$

(Sim, eu sei que funções de computação de adição, multiplicação e contagem, mas é fácil convertê-las em versões de decisão de seus respectivos problemas.)

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

(c) Portanto, para contar , mesmo que você não consiga obter uma expressão equivalente no 2-CNF, usando o método descrito em (b), é possível obter uma expressão 2-CNF equisatisfatória .

Então sim, o 2-SAT pode contar.

$NL$ $|M|$ $NL$

Martin Seymour
fonte

Re (c), se você acredita na minha resposta, uma expressão 2-CNF equisatisfazível pode ser convertida em uma expressão 2-CNF equivalente de boa-fé.

Yuval Filmus

-

$-$

$~$

Você pode ler minha resposta e ver por si mesmo. Observe que não há limites de tempo / espaço neste caso.

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$

$~$

Propriedades expressáveis ​​em 2-CNF ou 2-SAT

Respostas:

Propriedades expressáveis em 2-CNF ou 2-SAT