Universal Quantificadores em QBFs

Question

Eu estive olhando na redução de/para o TQBF linguagem e conseguiram ficar preso em algo que certamente não é verdadeiro (ou, se é verdade eu estou faltando um significativo custo computacional associado a ele), com respeito à simplificação TQBF instâncias.

Por uma questão de simplicidade, vamos restringir a atenção para TQBF instâncias na forma normal prenex e CNF sem variáveis livres.Minha hipótese (o que eu fortemente suspeito é errado, mas têm sido incapazes de encontrar um contra-exemplo) é que tal um TQBF é satisfatível se e somente se o TQBF que resulta da remoção de todas as instâncias do universalmente quantificadas as variáveis da sentença é satisfatível.Por exemplo, tomemos o seguinte exemplo:

$\existe um \forall b \existe c \forall d$ $\psi(a,b,c,d)$

$\psi(a,b,c,d) = ( eg um \vee b \vee c)\cunha ( eg b \vee eg c \vee d)\wedge (a \vee c \vee eg d)$

Primeiro, eu afirmo que esta instância não é satisfatível (facilmente verificável com a mão).Se aplicarmos o método que descrevemos acima, obtemos o seguinte "core":

$\existe um \existe c$ $\phi(a,c)$,

$\phi (a,c) = ( eg um \vee c)\cunha ( eg c) \wedge (a \vee c)$

o que não é claramente insatisfatória.Se, em vez disso exemplo, vamos olhar para este:

$\existe um \forall b \existe c \forall d$ $\psi(a,b,c,d)$

$\psi(a,b,c,d) = ( eg um \vee b \vee eg c)\cunha ( eg b \vee c \vee d)\wedge (a \vee c \vee eg d)$

que é claramente insatisfatória (conjunto c true, false) e que tem um "núcleo" do

$\existe um \existe c$ $\phi(a,c)$,

$\phi (a,c) = ( eg um \vee eg c)\cunha (c) \wedge (a \vee c)$

que também é satisfatível com as mesmas configurações de variáveis.

Se este método sempre funciona, o que parece sugerir que há uma redução de TQBF para SENTOU-se em tempo linear no número de quantificadores universal e o número de ocorrências do universalmente quantificadas as variáveis na fórmula, mostrando que TQBF é NP-Completo (já é conhecido por ser PSPACE-Completo e, portanto, NP-Difícil, portanto, se ele está em NP é NP-Completo) e, além disso, que NP=PSPACE.Eu seria totalmente atordoado, se este é o caso, mas eu tenho sido incapaz de encontrar um contra-exemplo (ou a falta de um custo computacional na redução que faz com que não seja em tempo polinomial).O que eu estou ausente?

Answer 1

A sua intuição estava certa.Ele não funciona.Aqui é um contra-exemplo.

Considere $\forall um \existe b \varphi(a,b)$ onde $\varphi(a,b) = (a \lor eg b) erra ( eg um \lor b)$.Esta instrução for avaliada como true.

No entanto, se removermos $a$ seguir o procedimento, obtemos $\existe b \psi(b)$ onde $\psi(b) = (( eg b) erra (b))$;e que a instrução for avaliada como false.

Uma maneira de entender por que o seu método não funciona é que $\forall um \existe b \varphi(a,b)$ não é equivalente a $\existe b \forall um \varphi(a,b)$.No máximo, seu método pode funcionar se todos os $\forall$'s estão do lado de dentro, isto é, por uma frase do formulário $\existe \cdots \existe \forall \cdots \forall$, mas não para qualquer outro padrão de $\existe$ e $\forall$.