Clasificación de variantes del problema de satisfacción intratable / tratable

20

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 , ...NP

Algunas otras variantes son manejables: - SAT , Planar-NAE- SAT , ...2SATSAT

¿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 )?SATNPP


  1. NND. Ratner y M. Warmuth (1986) no pueden encontrar la solución más corta para la extensión N x N del 15-Puzzle .
Vor
fuente
@mrm: gracias, no conocía el artículo de Schaefer ( dl.acm.org/citation.cfm?doid=800133.804350 )
Vor
1
Eliminé "publicar su favorito", porque este es un ejemplo de libro de texto de lo que no debe preguntar en Stack Exchange . (Sí, funciona hasta cierto punto en Ciencias de la Computación Teórica , pero ese es un caso especial debido a la audiencia altamente atípica.)
Gilles 'SO- deja de ser malvado'

Respuestas:

18

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

Si SAT está parametrizado por un conjunto de relaciones permitidas en cualquier caso, entonces solo hay 6 casos manejables: 2-SAT (es decir, cada cláusula es binaria), Horn-SAT, dual-Horn-SAT, affine-SAT (soluciones a lineal ecuaciones en GF (2)), 0-válido (relaciones satisfechas por la asignación all-0) y 1-válido (relaciones satisfechas por la asignación all-1).

NPNP

NPP

Variantes más recientes y / o "extrañas"

k

k

ϕG(ϕ)ϕ

G(ϕ)ϕϕG

k=4Pk=5NP

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.

NPNPkk3NP

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 .

Juho
fuente