Recientemente encontré en un artículo [1] una versión simétrica especial de SAT llamada 2/2/4-SAT . Pero hay muchas variantes completas de , por ejemplo: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...
Algunas otras variantes son manejables: - SAT , Planar-NAE- SAT , ...
¿Existen documentos de encuesta (o páginas web) que clasifiquen todas las variantes (extrañas) de que se ha demostrado que son NP completas (o en P )?
- D. Ratner y M. Warmuth (1986) no pueden encontrar la solución más corta para la extensión N x N del 15-Puzzle .
Respuestas:
Resultados clásicos y conocidos
Según lo mencionado por Standa Zivny sobre la pregunta relacionada de CSTheory, ¿qué problemas de SAT son fáciles? , hay un resultado bien conocido por Schaefer de 1978 (citando la respuesta de Zivny):
Variantes más recientes y / o "extrañas"
Variantes lineales de CNF
Aunque quizás no sea exótico o extraño, algunas variantes bien conocidas, como NAE-SAT ( SAT no igual) y XSAT (SAT exacto; exactamente un literal en cada cláusula a 1 y todos los demás literales a 0), de Se han investigado problemas de satisfacción en el entorno lineal . Las cláusulas de una fórmula lineal por pares tienen como máximo una variable en común. Curiosamente, el estado de complejidad no se sigue del Teorema de Schaefer.
Algunos aspectos adicionales con respecto a la complejidad de NAE-SAT y XSAT bajo ciertos supuestos probablemente todavía están abiertos. Para más detalles, ver por ejemplo Porschen y Schmidt, On Some SAT-Variants over Linear Formulas, 2009 y Porschen et al., Complexity Results for Linear XSAT-Problems, 2010 .
fuente