Busqué en Internet, pero no pude encontrar ninguna 'gran lista' de variantes del problema SAT.
Aparte del (común)
- SE SENTÓ,
- k-SAT,
- MAX-kSAT,
- Medio SAT,
- XOR-SAT,
- NAE-SAT
¿Qué más variantes hay?
(también será realmente útil si se dan clases de complejidad (cuando sea posible))
cc.complexity-theory
sat
big-list
Subhayan
fuente
fuente
Respuestas:
(Hacer que el comentario sea una respuesta solicitada y expandirse un poco).
"Una mente curiosa" debería leer el teorema de dicotomía de Schaefer y la generalización de Allender et al. eso muestra que cada posible variante SAT es trivial o está en una de las seis clases de complejidad conocidas:
fuente
Esta lista será muy larga;) Estas son algunas de mis variantes favoritas (NP-complete) de SAT:
Ver: Dahlhaus, Johnson, Papadimitriou, Seymour, Yannakakis, La complejidad de los cortes multiterminales, SIAM Journal of Computing 23 (1994) 864-894
PLANAR DE 4 LÍMITES 3SAT CONECTADO 3 (cada cláusula contiene exactamente 3 variables distintas, cada variable aparece como máximo en 4 cláusulas, el gráfico de incidentes de bipatita es plano y está conectado a 3)
Ver: Kratochvíl, un problema especial de satisfacción planar y una consecuencia de su integridad NP, Matemática aplicada discreta. 52 (1994) 233-252
MONOTONE CUBIC 1-IN-3SAT (MONOTONE-1-IN-3SAT en el que cada variable aparece exactamente 3 veces)
Ver: Moore y Robsen, problema de inclinación dura con mosaicos simples, cálculo discreto. Geom 26 (2001) 573-590
Ver este post .
fuente
En el "lado NP-completo" me encontré con estas variantes (también hice una pregunta similar sobre cs.stackexchange):
fuente
fuente
Además de la lista anterior, también hay:
fuente
Existe una conexión muy clásica entre la lógica y el álgebra, que se remonta al origen de la lógica moderna y el trabajo de George Boole. Una fórmula en lógica proposicional puede interpretarse como un elemento de un álgebra booleana. Las constantes lógicas verdadero y falso convierten en las nociones algebraicas del elemento superior e inferior de una red. Las operaciones lógicas de conjunción, disyunción y negación se convertirán en operaciones algebraicas de encuentro, unión y complementación en el álgebra booleana. Esta conexión se enfatiza menos en los tratamientos modernos de lógica, pero es particularmente interesante en el contexto de su pregunta. El álgebra nos permite alejarnos de muchos detalles específicos del problema y encontrar generalizaciones de un problema que se aplicarán a muchas situaciones diferentes.
En el caso específico de SAT, la pregunta algebraica que uno puede hacerse es qué sucede cuando interpretamos fórmulas en redes más generales que las álgebras booleanas. En el lado lógico, puede generalizar el problema de la satisfacción de la lógica proposicional a la lógica intuicionista. De manera más general, puede generalizar el problema de satisfacción de proposiciones al de determinar si una fórmula, cuando se interpreta sobre una red limitada (una con top y botto), define el elemento inferior de la red. Esta generalización le permite tratar los problemas en el análisis del programa como problemas de satisfacción.
Otra generalización es la lógica de primer orden libre de cuantificadores donde se obtiene la cuestión de la Módulo de satisfacción a la teoría. Es decir, además de tener variables booleanas, también tiene variables de primer orden y símbolos de función y desea saber si una fórmula es satisfactoria. En este punto, puede hacer preguntas sobre fórmulas en aritmética, teorías de cadenas o matrices, etc. Por lo tanto, obtenemos una generalización estricta y muy útil de SAT que tiene muchas aplicaciones en sistemas, seguridad informática, lenguajes de programación, verificación de programas, planificación , inteligencia artificial, etc.
fuente