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 ϕ .
¿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 ?
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.
¿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?
- Uriel Feige y Dorit Ron, Buscando camarillas ocultas en tiempo lineal , proc. DMTCS. AM, 2010, 189-204.
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 )
fuente
fuente
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.
fuente