Ist Fast-2-SAT NP-hart?

10

Ist ein CNF-SAT-Problem NP schwierig, wenn die Gesamtzahl (aber nicht die Breite) der 3-oder-mehr-Term-Klauseln oben durch eine Konstante begrenzt ist? Was ist konkret, wenn es nur eine solche Klausel gibt?

np-hardness sat upper-bounds dspyz
quelle

8

Wenn es nur eine solche Klausel ist

mit mehr als 2 Begriffe, solche Formeln zu lösen ist trivialerweise in

. Wenn

hat

Begriffe, versuchen jedes der

Teilzuweisungen , die genügen

, dann die restlichen 2-SAT Formel lösen die bekannten linearen Zeitverfahren verwendet wird . Schließlich finden Sie eine Lösung für die gesamte Formel oder beweisen, dass sie in der Zeit

nicht zufriedenstellend ist , wobei

die Anzahl der Variablen in der gesamten Formel nicht überschreiten kann.

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Kyle Jones

@KyleJones Aber eine einzelne Klausel mit

Literalen hat

zufriedenstellende Zuweisungen, nicht nur

. Da

in der Frage nicht begrenzt ist, ergibt dieser Ansatz einen Exponentialzeitalgorithmus.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

David Richerby

2

@DavidRicherby Um die Klausel zu erfüllen, müssen Sie nur eines der Literale als wahr auswerten lassen. Danach kann die Klausel ignoriert werden und es bleibt nur noch eine 2-SAT-Formel übrig.

Literale bedeutet, dass Sie nur

Zuweisungen ausprobieren müssen .

k

$k$

k

$k$

Kyle Jones

14

Es ist erwähnenswert, dass das Problem NP-hart wird, wenn die Beschränkung leicht gelockert wird.

Bei einer festen Anzahl von Klauseln, die ebenfalls eine begrenzte Größe haben, liegt die durchschnittliche Anzahl von Literalen in einer Klausel so nahe bei 2, wie man möchte, wenn eine Instanz mit genügend Variablen berücksichtigt wird. Wie Sie hervorheben, gibt es dann eine einfache Obergrenze, die polynomisch ist, wenn die Klauselgröße begrenzt ist.

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

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

Diese Reduzierung zeigt auch, dass selbst die Version, in der die "großen" Klauseln auf 3 Literale beschränkt sind, NP-hart ist.

Der verbleibende Fall ist, wenn die wenigen großen Klauseln keine begrenzte Größe haben; Jede große Klausel scheint das Problem schwieriger zu machen. Siehe das SODA 2010-Papier von Pǎtraşcu und Williams für den Fall von zwei Klauseln: Sie argumentieren, wenn dies in subquadratischer Zeit möglich wäre, hätten wir bessere Algorithmen für SAT. Es könnte eine Ausweitung ihres Arguments auf weitere Klauseln geben, die den Nachweis erbringen würden, dass Ihre Obergrenze nicht verbessert werden kann (modulo irgendeine Form der exponentiellen Zeithypothese).

András Salamon
quelle

nur tangential verwandt, aber es gibt ein kürzlich veröffentlichtes ECCC-Papier, das "fast 2-SAT" auf andere Weise formuliert und eine starke Härte beweist: eccc.hpi-web.de/report/2013/159

Sasho Nikolov

8

OK ich habe es. Die Antwort ist nein. Dies kann in Poly-Zeit gelöst werden. Wählen Sie für jede Klausel mit drei oder mehr Begriffen ein Literal aus und setzen Sie es auf true. Lösen Sie dann das verbleibende 2-Sat-Problem. Wenn jemand eine Lösung bietet, ist dies eine Lösung für das Gesamtproblem. Da die Anzahl der Klauseln mit drei oder mehr Begriffen festgelegt ist (z. B. c), läuft dies in O (m ^ (c) * n), wenn alle diese Klauseln die Größe <= m haben. O (m ^ c) zum Durchlaufen jeder möglichen Auswahl, mal O (n) zum Lösen des verbleibenden 2-Sat-Problems.

dspyz
quelle

m

$m$

Dies liegt daran, dass m implizit durch die Anzahl der Atome begrenzt ist. Offensichtlich kann eine Klausel nicht mehr Literale enthalten, als das Problem Atome enthält. Vielleicht hätte ich m <= n

dspyz

Ist Fast-2-SAT NP-hart?

Antworten: