Asignación para que la fórmula sea insatisfactoria

8

Imaginemos que tenemos una fórmula satisfactoria El problema a resolver es "¿Hay una asignación para las variables que hará F insatisfactorio? ". Una forma de resolver es encontrar todas las soluciones para F en términos de variables y si el recuento es < , la solución que falta será la respuesta, pero la complejidad de este algoritmo es enorme, si El número de tales asignaciones es pequeño. $F(A_0, A_1,...A_k,S_0,...,S_n)$ $(S_0,...,S_n)$ $S_0,...,S_n$ $2^n$

Mis preguntas son:

¿Hay alguna manera de resolver el problema con menos llamadas de solucionador SAT?
¿Es un problema bien conocido en teoría (lo que debería googlear para leer sobre él)?

logic satisfiability sat-solvers Grigor Aghanyan
fuente

1

"lo que hará que F sea insatisfactorio", eso no tiene sentido. ¿Simplemente quiere decir "no satisface F"? Entonces estás hablando del problema TAUTOLOGÍA (resp. Es complemento).

Raphael

Ignorando el hecho de que la pregunta no tiene sentido, creo que tratar de encontrar una solución a podría ser lo que está buscando.

\neg F (A_{0}, A_{1}, \dots, A_{k}, S_{0}, \dots, S_{n})

$\neg F(A_0,A_1,\ldots, A_k,S_0,\ldots, S_n)$

Dave Clarke

Quizás no estaba claro. Después de aplicar asignaciones para tendremos otra fórmula y esto debe ser insatisfactorio.

(S_{0}, . . ., S_{n})

$(S_0,...,S_n)$

G (A_{0}, . . ., A_{k})

$G(A_0 ,..., A_k)$

Grigor Aghanyan

6

Su problema es el problema canónico -completo: Como tal, se cree que es más difícil que SAT (que es ). Resolverlo con unas pocas llamadas al oráculo SAT es similar a resolver el SAT de manera eficiente (la pregunta P vs. NP), aunque podría ser que mientras , por lo que en cierto sentido Hay más esperanza para su problema que para el SAT mismo. $\Sigma_2^P$

\exists \vec{S} \forall \vec{A} \neg F (\vec{A}, \vec{S}) .

$\exists \vec{S} \forall \vec{A} \lnot F(\vec{A},\vec{S}).$

Σ_{1}^{P}

$\Sigma_1^P$

Σ_{2}^{P} = Σ_{1}^{P}

$\Sigma_2^P = \Sigma_1^P$

P \neq N P

$P \neq NP$

Yuval Filmus
fuente

Exactamente. Gracias por la respuesta. Entonces, ¿la solución con llamadas de solucionador "no es una mala solución"? Algún enlace para documentos sobre este problema me ayudará mucho.

2^{n}

$2^n$

Grigor Aghanyan

Prácticamente hablando, podría haber heurísticas que funcionen bien para algunos problemas, pero no tengo conocimiento de ninguno. La jerarquía polinómica (que contiene ) debe estar cubierta en cualquier libro de texto sobre complejidad computacional.

Σ_{2}^{P}

$\Sigma_2^P$

Yuval Filmus

4

Este es un problema bien conocido: es el problema 2QBF. Desafortunadamente, es significativamente más difícil que el SAT. Hay solucionadores QBF disponibles. Puede intentar encontrar un solucionador QBF (o, mejor aún, un solucionador 2QBF) y ver si puede resolver su fórmula. Sin embargo, los solucionadores QBF no escalan tan bien como los solucionadores SAT; QBF es significativamente más difícil que SAT.

Consulte https://cstheory.stackexchange.com/q/11022/5038 y http://www.qbflib.org/ para obtener algunos recursos que pueden ser útiles.

DW
fuente

Asignación para que la fórmula sea insatisfactoria

Respuestas: