¿Es posible incorporar una solución para SAT?

10

Estoy interesado en instancias individuales "difíciles" de problemas NP-completos.

Ryan Williams discutió el problema SAT0 en el blog de Richard Lipton . SAT0 pregunta si una instancia SAT tiene la solución específica que consiste en todos los 0. Esto me hizo pensar en construir instancias SAT que probablemente sean "difíciles".

Considere una instancia SAT con cláusulas my variables n , donde α = m / n es "lo suficientemente grande", en el sentido de que cae en la región más allá de la transición de fase, donde casi todas las instancias son insatisfactorias. Sea x una asignación aleatoria a los valores de ϕ .ϕmnα=m/nxϕ

¿Es posible modificar para obtener una nueva instancia ϕ | x , de modo que ϕ | x es "en gran medida similar" a ϕ , pero de modo que x es una asignación satisfactoria para ϕ | x ?ϕϕ|xϕ|xϕxϕ|x

Por ejemplo, uno podría intentar agregar a cada cláusula un literal elegido al azar de la solución, que aún no aparece en la cláusula. Esto garantizará que sea ​​una solución.x

¿O es esto desesperado, lo que lleva a un algoritmo rápido para encontrar la solución "oculta", en la línea del siguiente artículo reciente?

Soy consciente de la discusión de Cook y Mitchell y del trabajo al que hacen referencia. Sin embargo, no pude encontrar nada sobre lo que le sucede a la estructura de una fórmula cuando uno intenta incorporar explícitamente una tarea satisfactoria. Si esto es folklore, ¡los punteros serían muy bienvenidos!

  • Stephen A. Cook y David G. Mitchell, Encontrando instancias difíciles del problema de satisfacción: una encuesta , serie DIMACS en Matemática discreta y ciencias de la computación teóricas 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. ( PS )
András Salamon
fuente

Respuestas:

13

φφψxψxxf:{0,1}n{0,1}nxy=f(x)yxxfxx

Boaz Barak
fuente
ϕψxϕψx
6

mn>4.3

xnmkp=12xϕ|xϕϕ|xxllϕϕ|xϕϕ|x

ϕ|xϕ

ϕx

  1. ϕxx

  2. mxmxxx

xxx

Giorgio Camerani
fuente
Gracias por los comentarios, estoy de acuerdo en que se cambiaría el espacio de la solución. Como se indica en la pregunta, quiero saber si hay una manera de modificar la fórmula para ocultar una solución. Agregar los literales a cada cláusula significa una prueba de existencia de que uno puede agregar la solución a la fórmula. No quise sugerir que este es el único, mejor o incluso un buen método.
András Salamon
xϕ|xϕx
Idealmente, uno quiere un método computable de polytime que no cambie el espacio de la solución "demasiado" ...
András Salamon
n3log n
3lognn2nn3logn
4

La mejor manera de generar instancias difíciles de problemas NP-completos que conozco es usar el mapeo de Cook para reducir las instancias cuidadosamente seleccionadas de ciertos otros problemas NP difíciles (como el problema de logaritmo discreto o la factorización de enteros) a SAT. Estos son los mismos "problemas difíciles" que utilizan los matemáticos para garantizar la seguridad criptográfica en protocolos como RSA y Diffie-Hellman.

Philip White
fuente
Referencias, por favor?
gphilip
No estoy seguro de por qué el voto negativo de esta respuesta. quien lo hizo debería explicarlo.
Suresh Venkat