Almost-2-SAT NP-hard?

10

Un problème CNF SAT NP est-il difficile lorsque le nombre total (mais pas la largeur) des clauses de 3 termes ou plus est limité au-dessus par une constante? Qu'en est-il spécifiquement quand il n'y a qu'une seule clause de ce type?

np-hardness sat upper-bounds dspyz
la source

8

S'il n'y a qu'une telle clause

avec plus de 2 termes, la résolution de ces formules est trivialement dans

. Si

a

termes, essayez chacune des

affectations partielles qui satisfont

, puis résolvez la formule 2-SAT restante en utilisant la méthode connue du temps linéaire. Finalement, vous trouverez une solution pour la formule entière ou prouverez qu'elle n'est pas satisfaisante en temps

, où

ne peut pas dépasser le nombre de variables dans la formule entière.

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Kyle Jones

@KyleJones Mais une seule clause avec

littéraux a

affectations satisfaisantes, pas seulement

. Puisque

n'est pas borné dans la question, cette approche donne un algorithme à temps exponentiel.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

David Richerby

2

@DavidRicherby Pour satisfaire la clause, il suffit de faire en sorte que l'un des littéraux soit vrai. Après cela, la clause peut être ignorée et il ne vous reste qu'une formule 2-SAT.

littéraux signifie que vous n'avez qu'à essayer

affectations.

k

$k$

k

$k$

Kyle Jones

14

Il convient de noter que le problème devient NP-difficile lorsque la restriction est légèrement assouplie.

Avec un nombre fixe de clauses qui sont également de taille limitée, le nombre moyen de littéraux dans une clause est aussi proche de 2 que l'on veut, en considérant une instance avec suffisamment de variables. Comme vous le faites remarquer, il existe alors une borne supérieure simple qui est polynomiale si la taille de la clause est bornée.

$2 + \epsilon$ $\epsilon > 0$

$m$ $(2+\epsilon)$ $m(1 - \epsilon)/\epsilon$ $\epsilon$

Cette réduction montre également que même la version où les "grandes" clauses sont limitées à 3 littéraux est NP-hard.

Le cas restant est celui où les quelques grandes clauses ne sont pas de taille limitée; chaque grande clause semble rendre le problème plus difficile. Voir le document SODA 2010 de Pǎtraşcu et Williams pour le cas de deux clauses: ils soutiennent que si cela peut être fait en temps sub-quadratique, alors nous aurions de meilleurs algorithmes pour SAT. Il pourrait y avoir une extension de leur argument à plus de clauses, ce qui fournirait la preuve que votre borne supérieure ne peut pas être améliorée (modulo une certaine forme de l'hypothèse de temps exponentielle).

András Salamon
la source

seulement tangentiellement liés, mais il y a un document récent d'ECCC qui formule "presque 2-SAT" d'une manière différente et prouve une forte dureté: eccc.hpi-web.de/report/2013/159

Sasho Nikolov

8

OK j'ai compris. La réponse est non. Cela peut être résolu en poly-temps. Pour chaque clause de 3 termes ou plus, sélectionnez un littéral et définissez-le sur true. Résolvez ensuite le problème des 2 sat. Si quelqu'un fournit une solution, c'est une solution au problème global. Puisque le nombre de clauses à 3 termes ou plus est fixe (disons c), alors si toutes ces clauses ont une taille <= m, cela s'exécute en O (m ^ (c) * n). O (m ^ c) pour parcourir chaque sélection possible, fois O (n) pour résoudre le problème à 2 sat.

dspyz
la source

m

$m$

C'est parce que m est implicitement limité par le nombre d'atomes. De toute évidence, une clause ne peut pas avoir plus de littéraux qu'il n'y a d'atomes dans le problème. J'aurais peut-être dû clarifier m <= n

dspyz

Almost-2-SAT NP-hard?

Réponses: