Equivalência de Krom fórmulas difíceis de ser tratados?

Question

Suponha que eu tenha duas Krom fórmulas $\psi_1, \psi_2$.Krom fórmulas são fórmulas proposicionais em CNF com 2 literais em cada cláusula.Cada um literal pode ser negado ou unnegated.Em outras palavras, $\psi_1,\psi_2$ 2-CNF fórmulas.Por exemplo:

$(x_1 \vee eg x_2) erra ( eg x_2 \vee x_3 ) erra (x_3 \vee x_4)$

Eu quero decidir se $\psi_1,\psi_2$ são logicamente equivalentes, isto é, $\psi_1 \leftrightarrow \psi_2$.Equivalentemente, eu quero testar se $F=(\psi_1 \vee eg\psi_2)\cunha ( eg \psi_1 \vee \psi_2)$ é verdadeiro para todas as atribuições de $x_1,\dots,x_n$.

Este problema é tratável?

Answer 1

Sim, a equivalência pode ser verificada em tempo polinomial (de fato, em tempo quadrático).

Eu descreverei como testar se $ \ psi_1 \ lor \ neg \ psi_2 $ é verdade para todas as atribuições. Você pode fazer o mesmo para $ \ neg \ psi_1 \ lor \ psi_2 $ e use isso para testar se $ F $ é uma tautologia, ou seja, se $ \ psi_1, \ psi_2 $ são logicamente equivalentes.

Eu farei isso verificando se $ \ psi_1 \ lor \ neg \ psi_2 $ é falso para qualquer tarefa, ou em outras palavras, se $ \ NEG (\ psi_1 \ lor \ neg \ psi_2) $ é satisfatório. Observe que

$$ \ NEG (\ psi_1 \ lor \ neg \ psi_2)=neg \ psi_1 \ land \ psi_2, $$

Então, é suficiente para testar a satisfomoção da $ \ neg \ psi_1 \ land \ psi_2 $ onde $ \ psi_1, \ psi_2 $ são fórmulas Krom (2-CNF).

Suponha que $ \ psi_1= c_1 \ terra \ cdoz \ land c_k $ onde $ c_i $ é a cláusula $ i $ th na $ \ psi_1 $ . Então

$$ \ Neg \ psi_1= (\ NEG C_1) \ lor \ cdots \ lor (\ neg c_k). $$

Portanto

$$ \ begin {alinhar *} \ neg \ psi_1 \ land \ psi_2 &= (\ neg c_1) \ lor \ cdots \ lor (\ neg c_k)) \ terra \ psi_2 \\ &= (\ neg c_1 \ land \ psi_2) \ lor \ cdots \ lor (\ neg c_k \ land \ psi_2). \ final {alinhar *} $$

agora, $ \ neg \ psi_1 \ terra \ psi_2 $ é satisfatório IFF $ \ neg c_i \ land \ psi_2 $ é satisfatório para alguma $ i $ . Então, podemos iterar sobre $ i $ e teste a satisfomoção de cada $ \ neg c_i \ terra \ psi_2 $ ; Se algum deles for satisfatório, então $ \ neg \ psi_1 \ lor \ psi_2 $ é satisfatório e $ F $ não é uma tautologia e $ \ psi_1, \ psi_2 $ não são logicamente equivalentes.

Como testar a satisfomoção da $ \ NEG C_I \ Land \ psi_2 $ ? Bem, $ c_i $ tem o formulário $ (\ ell_1 \ lor \ ell_2) $ onde $ \ ell_1, \ ell_2 $ são dois literais, então $ \ neg c_i \ land \ psi_2 $ tem o formulário < Classe Span="Recipiente de Matemática"> $ \ Neg \ Ell_1 \ Land \ Neg \ Ell_2 \ Land \ PSI_2 $ . Esta é também uma fórmula Krom (2-CNF), para que você possa testar sua satisfomoção usando o algoritmo padrão de tempo polinômico. Você faz um número linear desses testes, portanto, o tempo total de funcionamento é polinômio. Na verdade, é quadrático, pois a satisfação de testes pode ser feita em tempo linear.

Answer 2

Lembro 2-SÁB solução que utiliza fortemente ligado componentes:vamos construir um grafo com vértices $x_1,\ldots,x_n, \lnot x_1, \ldots, \lnot x_n$, e podemos substituir cada cláusula $x_i \lor x_j$ com bordas $\lnot x_i \para x_j$ e $\lnot x_j \para x_i$.Um exemplo de aqui:

Para satisfazer a fórmula, é necessário e suficiente para atribuir vértices de forma que não haja contradições no gráfico (sem borda $true \false$).Vamos usar estes gráficos para verificação de equivalência.

1. Nós construímos esses gráficos $G_1$ e $G_2$ para ambas as fórmulas $F_1$ e $F_2$.
2. Se há um ciclo $x_i \leadsto \lnot x_i \leadsto x_i$ em um gráfico, em seguida, sua fórmula não tem soluções.Podemos verificar que ambas as fórmulas são solúvel/insolúvel.
3. Se existe um caminho de formulário $x_i \leadsto \lnot x_i$ (da mesma forma para o caso $\lnot x_i \leadsto x_i$), sabemos que para satisfazer a fórmula deve-se selecionar $x_i$ para ser falso (caso contrário, temos uma contradição).Lembramos que essa escolha.Utilizando o gráfico, podemos atribuir valores a todos os vértices alcançáveis a partir de $\lnot x_i$ (eles devem ser verdadeiras).Novamente, verifique se ambas as fórmulas feitas exatamente a mesma decisão no final.
4. Remover todas as bordas para/de todos os vértices a partir dos gráficos.
5. Agora, $F_1$ e $F_2$ são equivalentes $\iff$ os restantes gráficos são equivalentes no seguinte sentido:para qualquer $v_1,v_2$ caminho $v_1 \leadsto v_2$ existe no $G_1$ iff ela existe em $G_2$.Isso pode ser verificado em, no máximo, $O(|V|\cdot|E|)$ tempo (basta executar DFS a partir de cada um dos vértices e verifique que ela tem visitado os mesmos vértices para ambos os gráficos).Talvez isso pode ser feito mais rápido.

Prova:

$\Esquerda$:evidente, pois após fechamento transitivo de gráficos nós vamos ter as mesmas implicações em ambas as fórmulas.

$ ightarrow$:Por contradição.Wlog assumirmos que existe um caminho $v_1 \leadsto v_2$ no $G_1$ que não existe na $G_2$.Isso significa que a atribuição de $v_1 := true$, $v_2 := false$ é possível, em $F_2$ (como não há nenhum caminho $v_1 \leadsto v_2$), mas é inviável, em $F_1$.

Nomeadamente, a seguinte atribuição satisfaz $F_2$:

• $true,$ para todos os vértices alcançáveis a partir de $v_1$.
• $false$ de todos os vértices que podem chegar a $v_2$.
• Remover todos os conhecidos vértices (acima mencionadas e os respectivos complementos) do gráfico.Todos os restantes vértices criar componentes conectados.Nós cores componentes conectados em $true,$, e componentes conectados correspondente à sua complementa - em $false$ (ver nota abaixo).

Esta atribuição não tem nenhuma contradição, já que não pode haver borda $u \v$ de forma $true \false$:

• Se u $$ pertence a um componente que estava cheio de cor $true,$, e , em seguida, tais $v$ também deve ser verdadeira.
• Caso contrário, significa que u $$ é acessível a partir de $v_1$, e , portanto, $v$ também é acessível a partir $v_1$ e deve ser verdade. $\blacksquare$

Nota técnica:para cada variável $x_i$ existem dois vértices: $v_i$ e $\lnot v_i$ - e pode-se perguntar se ele vai levar a alguns problemas com as atribuições.A resposta é que, depois do passo 4), $v_i$ e $\lnot v_i$ irá situar-se em dois componentes diferentes (além disso, eles são simétricas: $u \v$ em um componente significa $\lnot u \a \lnot v$ em outra).Portanto, qualquer que seja a decisão que tomamos para u $$ em um componente, podemos fazer o oposto decisão para $\lnot u$ em uma outra.