Es Almost-2-SAT NP-hard?

10

¿Es un problema CNF SAT NP difícil cuando el número total (pero no el ancho) de las cláusulas de 3 o más términos está limitado por una constante? ¿Qué pasa específicamente cuando solo hay una de esas cláusulas?

np-hardness sat upper-bounds dspyz
fuente

8

Si sólo hay una tal cláusula con más de 2 términos, la solución de tales fórmulas es trivialmente en . Si tiene términos, pruebe cada una de las asignaciones parciales que satisfacen , luego resuelva la fórmula 2-SAT restante utilizando el método conocido de tiempo lineal. Eventualmente encontrará una solución para toda la fórmula o probará que no es satisfactoria en el tiempo , donde no puede exceder el número de variables en toda la fórmula.

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Kyle Jones

@KyleJones Pero una sola cláusula con literales tiene asignaciones satisfactorias, no solo . Como no está acotado en la pregunta, este enfoque proporciona un algoritmo de tiempo exponencial.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

David Richerby

2

@DavidRicherby Para satisfacer la cláusula solo necesita hacer que uno de los literales evalúe verdadero. Después de eso, la cláusula puede ignorarse y solo le queda una fórmula 2-SAT. literales significa que solo tiene que probar asignaciones.

k

$k$

k

$k$

Kyle Jones

14

Vale la pena señalar que el problema se vuelve NP-duro cuando la restricción se relaja ligeramente.

Con un número fijo de cláusulas que también son de tamaño acotado, el número promedio de literales en una cláusula es tan cercano a 2 como uno quiera, considerando una instancia con suficientes variables. Como usted señala, existe un límite superior simple que es polinómico si el tamaño de la cláusula está limitado.

Por el contrario, si el número promedio de literales por cláusula es al menos para algunos fijos (pero arbitrariamente pequeños) , entonces el problema es NP-hard. $2 + \epsilon$ $\epsilon > 0$

Esto se puede demostrar reduciendo 3SAT a este problema, introduciendo nuevas cláusulas con 2 literales que son trivialmente satisfactorios. Supongamos que hay cláusulas en la instancia de 3SAT; para reducir el tamaño promedio de la cláusula a , es suficiente agregar nuevas cláusulas con dos literales. Como es fijo y positivo, la nueva instancia es de tamaño polinómico. $m$ $(2+\epsilon)$ $m(1 - \epsilon)/\epsilon$ $\epsilon$

Esta reducción también muestra que incluso la versión donde las cláusulas "grandes" están restringidas a 3 literales es NP-hard.

El caso restante es cuando las pocas cláusulas grandes no son de tamaño limitado; cada cláusula grande parece dificultar el problema. Vea el documento SODA 2010 de Pǎtraşcu y Williams para el caso de dos cláusulas: argumentan que si esto se puede hacer en tiempo subcuadrático, entonces tendríamos mejores algoritmos para SAT. Puede haber una extensión de su argumento a más cláusulas, lo que proporcionaría evidencia de que su límite superior no puede mejorarse (módulo de alguna forma de la hipótesis del tiempo exponencial).

András Salamon
fuente

solo relacionado tangencialmente, pero hay un documento reciente de ECCC que formula "casi 2-SAT" de una manera diferente y demuestra una fuerte dureza: eccc.hpi-web.de/report/2013/159

Sasho Nikolov

8

Ok, lo tengo La respuesta es no. Esto se puede resolver en poli-tiempo. Para cada cláusula de 3 o más términos, seleccione un literal y configúrelo como verdadero. Luego resuelva el problema restante de 2 sat. Si alguien proporciona una solución, entonces esa es una solución al problema general. Como el número de cláusulas de 3 o más términos es fijo (por ejemplo, c), si todas esas cláusulas tienen un tamaño <= m, entonces esto se ejecuta en O (m ^ (c) * n). O (m ^ c) para revisar cada selección posible, multiplicada por O (n) para resolver el problema restante de 2 sat.

dspyz
fuente

Pero la pregunta dice explícitamente que no tiene límites, por lo que este no es un algoritmo de tiempo polinómico.

m

$m$

David Richerby

Lo es, porque m está implícitamente limitada por el número de átomos. Obviamente, una cláusula no puede tener más literales que átomos en el problema. Quizás debería haber aclarado m <= n

dspyz

Es Almost-2-SAT NP-hard?

Respuestas: