Verifique a correção da eliminação do quantificador, usando SAT

8

Seja e sejam vetores de variáveis ​​booleanas. Eu tenho um predicado booleano em . Dou à minha amiga Priscilla . Em resposta, ela me fornece , um predicado booleano em , e ela afirma quex=(x1,,xn)y=(y1,,yn)nQ(x,y)x,yQ(x,y)P(x)x

P(x)y.Q(x,y),

ou em outras palavras, que

x.[P(x)y.Q(x,y)].

Eu gostaria de verificar sua reivindicação de alguma forma. Como a Priscilla pode me ajudar a verificar esta reivindicação?

Você pode assumir que e são representados como fórmulas CNF e que não são muito grandes (tamanho polinomial ou algo assim).PQ

Em um mundo ideal, seria incrível se eu pudesse reduzir o problema de verificação dessa reivindicação para SAT: eu tenho um solucionador de SAT e seria ótimo se eu pudesse usar o solucionador de SAT para verificar essa reivindicação. No entanto, tenho certeza de que não será possível formular o problema de verificar essa afirmação diretamente como uma instância SAT; testar a validade de uma fórmula 2QBF é quase certamente mais difícil que o SAT. (A direção é fácil de formular como uma instância SAT, mas a direção é difícil porque envolve inerentemente dois quantificadores alternativos.)

Mas suponha que Priscilla possa me dar alguma evidência adicional para apoiar sua afirmação. Existe alguma evidência adicional ou testemunha que Priscilla possa me dar, o que facilitaria a verificação de sua alegação? Em particular, há alguma evidência ou testemunha adicional que ela poderia me dar, o que facilitaria a formulação do problema de verificação de sua reivindicação como uma instância do SAT (na qual eu posso aplicar meu solucionador SAT)?

Um aspecto incomum da minha configuração é que estou assumindo (heuristicamente) que tenho um oráculo para o SAT. Se você gosta da teoria da complexidade, pode pensar assim: Estou assumindo o papel de uma máquina que pode computar coisas em (ou seja, em ), e estou procurando verificar se Priscilla está declaração usando um algoritmo em . Meus agradecimentos à MDX por essa maneira de pensar sobre as coisas.PNPΔ2PPNP


Minha motivação / aplicação: estou procurando fazer a verificação formal de um sistema (por exemplo, verificação de modelo simbólico), e uma etapa fundamental no raciocínio envolve a eliminação do quantificador (ou seja, começando com , obtenha ). Espero alguma maneira limpa de verificar se a eliminação do quantificador foi feita corretamente.QP

Se não houver uma solução que funcione para todos os possíveis fique à vontade para sugerir uma solução "sólida, mas não completa", ou seja, uma técnica que, para muitos permita-me verificar a equivalência reivindicada. (Mesmo que ele não verifique a reivindicação em alguns que satisfazem a reivindicação, ainda posso tentar isso como uma heurística, desde que nunca afirme inadequadamente ter verificado uma declaração falsa. Em qualquer , pode funcionar ou não; se não funcionar, não estou pior do que onde comecei.)P,QP,QP,QP,Q

DW
fonte
Se atribuirmos a Priscilla um onde y é irrelevante, não estamos resolvendo efetivamente ? Nesse caso, não há certificado que Priscilla possa fornecer a você, a menos que . Q(x,y)TAUTcoNPNP=coNP
Mdxn #
@ MDX, a coisa peculiar sobre essa configuração é que eu tenho um solucionador de SAT, que (empiricamente) parece quase sempre funcionar nos predicados que eu encontro na prática. Então, se me deremP(x),Q(x) e quer verificar x.P(x)Q(x)Eu posso alimentar (P(x)¬Q(x))(¬P(x)Q(x))no meu solucionador SAT; se achar que isso não é satisfatório, verifiqueix.P(x)Q(x)é verdade. Então, mesmo que isso resolva efetivamenteTAUT, ainda está tudo bem na prática. Ou entendi mal a essência do seu comentário?
DW
1
Ah, então eu suponho que você esteja assumindo o papel de uma máquina que decide problemas em PNP=Δ2P(ou o equivalente heurístico de)?
Mdxn #
@ MDX, sim, agora que você mencionou, é uma boa maneira de pensar sobre isso. Obrigado por sugerir essa perspectiva!
DW
Não acho que a first-order-logictag seja justificada. A questão é toda sobre fórmulas booleanas quantificadas.
Joe #

Respostas:

2

Aqui estão duas técnicas que eu consegui identificar:

  • Identifique uma função Skolem explícita. Suponha que Priscilla possa identificar uma função explícitaf de tal modo que

    x.P(x)Q(x,f(x))

    detém. Daí decorre que a afirmação de Priscilla está correta.

    Isso significa que Priscilla pode nos ajudar a verificar sua reivindicação, fornecendo uma função fpara que a proposição acima se mantenha. Podemos confirmar que a proposição acima é válida testando a seguinte fórmula para garantir a satisfação:

    ¬(P(x)Q(x,f(x))).

    Se essa fórmula não for satisfatória, a reivindicação de Priscilla foi verificada.

    Uma ressalva é que Priscilla precisa ser capaz de identificar uma função adequada f. Uma ressalva adicional é que precisamosfser concretamente representável de alguma forma concisa, digamos, como um circuito booleano de tamanho polinomial. No entanto, se essas condições forem atendidas, essa técnica deve funcionar.

  • Um argumento híbrido. Considere o caso especial desse problema, em que estamos quantificando sobre uma variável de um bit (em vez de umanvariável de bits); Acontece que o problema é fácil de resolver nesse caso. Isso sugere que tentamos encadear essa técnican vezes, cada vez que remover mais um pedaço y. Acontece que essa ideia às vezes funciona, mas nem sempre.

    Deixe-me explicar como verificar a alegação de Priscilla no caso em que y=(y1)é uma variável de um bit. Entãoy.Q(x,y) é equivalente a Q(x,False)Q(x,True). A última fórmula é no máximo duas vezes maior queQ, de tamanho ainda polinomial. Agora podemos usar nosso solucionador SAT para testar seQ(x,False)Q(x,True) é equivalente a P(x); a equivalência vale exatamente se a seguinte fórmula não for satisfatória:

    ¬(P(x)(Q(x,False)Q(x,True))).

    Portanto, se estivermos quantificando em um único bit, isso permitirá verificar se a eliminação do quantificador foi feita corretamente.

    Para resolver o problema original, aplique isso várias vezes. O trabalho de Priscilla será nos darn+1 predicados booleanos R0,R1,R2,,Rn de tal modo que

    Ri(x,(yi+1,,yn))y1,y2,,yi.Q(x,y).

    Nossa tarefa será verificar se todos esses predicados booleanos foram gerados corretamente. Podemos fazer isso testando seQ(x,y)R0(x,y), P(x)Rn(x),

    Ri+1(x,(yi+2,,yn))yi+1.Ri(x,(yi+1,,yn))for i=1,2,,n1.

    Observe que o último é uma instância de eliminação do quantificador com um único bit; portanto, já descrevemos como testá-lo corretamente usando um solucionador SAT. Também podemos testar seQR0 e PRusando um solucionador SAT diretamente. Então, podemos verificar se Priscilla gerouR0,,Rncorretamente. Se ela fez, então verificamos queP foi gerado adequadamente.

    Uma ressalva é que Priscilla precisa ser capaz de gerar o Ri's. Uma ressalva maior é que o tamanho de todo oRiprecisa ser razoável (digamos, de tamanho polinomial). Se Priscilla gerar oRiingenuamente, seu tamanho pode crescer exponencialmente com i, o que não é bom. Portanto, Priscilla precisará de uma maneira de simplificar a cada estágio; precisa existir alguma sequência deR0,,Rntodos com tamanho polinomial, e Priscilla precisa ser capaz de encontrar essa sequência. Isso não é de forma alguma garantido. Dito isto, se Priscilla puder fazer isso, essa técnica deve funcionar.

Não estou totalmente satisfeito com essas técnicas - elas são heurísticas incompletas e podem falhar em algumas / muitas instâncias de problemas -, portanto, eu ainda estaria interessado em ver outras maneiras de abordar esse problema.

DW
fonte