variaciones de SAT

14

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))

Subhayan
fuente
¿Cuál sería el propósito de esta lista?
Tyson Williams
2
Primero porque quería presentar una charla a algunos estudiantes universitarios. Estaba planeando hablar sobre las variaciones de SAT y mostrar algunas reducciones (no triviales) ... ya han tenido un curso introductorio en TOC, así que pensé que podría ser una buena idea ... Y LA SEGUNDA RAZÓN es el hecho no existe tal lista en internet, esta lista también servirá a cualquier mente curiosa que quiera saber acerca de las variantes.
Subhayan
11
No estoy seguro de cómo esta lista ayudará con su charla. En lugar de leer una lista arbitrariamente larga de variantes SAT, 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 variante SAT posible está completa para una de las seis clases de complejidad conocidas.
Tyson Williams
esa es una buena sugerencia ... gracias @TysonWilliams ... también puede convertir eso en una respuesta, aunque eso no es exactamente lo que estaba buscando, pero seguramente esto sea útil.
Subhayan

Respuestas:

17

(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:

  1. NP-complete
  2. P-completo
  3. NL-complete
  4. L-completo
  5. ⊕L-completo
  6. co-NLOGTIME
Tyson Williams
fuente
17

Esta lista será muy larga;) Estas son algunas de mis variantes favoritas (NP-complete) de SAT:

  • 3,3 ) -SAT (cada cláusula contiene al menos dos y como máximo tres literales, cada variable aparece exactamente en tres cláusulas; dos veces en su forma no negada, y una vez en su forma negada, y el gráfico de incidencia bipartita es plano)

    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

  • kk

    Ver este post .

usuario13136
fuente
44
Si encuentra interesante el último punto, también podría interesarle saber que # PLANAR-NAE-3SAT (soluciones de conteo) también es manejable, mientras que otras variantes SAT aparentemente simples como PLANAR-MONOTONE-2SAT son manejables (o incluso triviales) como un problema de decisión, pero # P-difícil de contar. Tenga en cuenta que la reducción desde el último enlace anterior (reducir PLANAR-NAE-kSAT a PLANAR-NAE-3SAT) no es parsimoniosa, y que # PLANAR-NAE-4SAT es # P-hard.
William Whistler
11

En el "lado NP-completo" me encontré con estas variantes (también hice una pregunta similar sobre cs.stackexchange):

Marzio De Biasi
fuente
7

SUNT(k)SUNTkSUNT(2)LSUNT(k)k3

Jan Johannsen
fuente
1

Además de la lista anterior, también hay:

  • #SAT: conteo de modelos
  • All-SAT: enumeración de modelos
qsp
fuente
1

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.

Vijay D
fuente