Czy Almost-2-SAT NP-hard jest trudny?

10

Czy problem CNF SAT NP jest trudny, gdy całkowita liczba (ale nie szerokość) klauzul 3-lub więcej-terminowych jest ograniczona stałą? A co powiesz konkretnie, kiedy istnieje tylko jedna taka klauzula?

np-hardness sat upper-bounds dspyz
źródło

8

Jeśli istnieje tylko jedna taka klauzula

ponad 2 kategoriach, rozwiązywania takich formuł jest trywialnie w

. Jeśli

ma

terminów, wypróbuj każde z

częściowych przypisań, które spełniają

, a następnie rozwiąż pozostałą formułę 2-SAT, stosując znaną metodę czasu liniowego. W końcu znajdziesz rozwiązanie dla całej formuły lub udowodnisz, że jest ona niezadowalająca w czasie

, gdzie

nie może przekraczać liczby zmiennych w całej formule.

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Kyle Jones,

@KyleJones Ale pojedyncza klauzula z literałami

ma

spełniających zadania, a nie tylko

. Ponieważ

nie jest ograniczone w pytaniu, to podejście daje algorytm czasu wykładniczego.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

David Richerby,

2

@DavidRicherby Aby spełnić klauzulę, wystarczy, że jeden z literałów ocenia prawdę. Następnie klauzulę można zignorować i pozostała tylko formuła 2-SAT.

literałów oznacza, że musisz tylko wypróbować

zadań.

k

$k$

k

$k$

Kyle Jones,

14

Warto zauważyć, że problem staje się trudny do NP, gdy ograniczenie jest nieco złagodzone.

Przy ustalonej liczbie klauzul, które również mają ograniczony rozmiar, średnia liczba literałów w klauzuli jest tak bliska 2, jak się chce, biorąc pod uwagę instancję z wystarczającą liczbą zmiennych. Jak zauważyłeś, istnieje wtedy prosta górna granica, która jest wielomianowa, jeśli rozmiar klauzuli jest ograniczony.

W przeciwieństwie do tego, jeśli średnia liczba literałów na klauzulę wynosi co najmniej dla niektórych ustalonych (ale dowolnie małych) , to problem jest trudny NP. $2 + \epsilon$ $\epsilon > 0$

Można to wykazać, redukując 3SAT do tego problemu, wprowadzając nowe klauzule z 2 literałami, które są banalnie zadowalające. Załóżmy, że w instancji 3SAT są klauzule ; aby zmniejszyć średnią wielkość klauzuli do , wystarczy dodać nowe klauzule z dwoma literałami. Ponieważ jest stałe i dodatnie, nowa instancja ma rozmiar wielomianowy. $m$ $(2+\epsilon)$ $m(1 - \epsilon)/\epsilon$ $\epsilon$

Ta redukcja pokazuje również, że nawet wersja, w której „duże” klauzule są ograniczone do 3 literałów, jest NP-trudna.

Pozostały przypadek ma miejsce, gdy kilka dużych klauzul nie ma ograniczonego rozmiaru; każda duża klauzula wydaje się utrudniać problem. Zobacz artykuł SODA 2010 Pǎtraşcu i Williamsa na temat dwóch klauzul: twierdzą, że jeśli można to zrobić w czasie subkwadratowym, to mielibyśmy lepsze algorytmy dla SAT. Może istnieć rozszerzenie ich argumentu na więcej klauzul, które dostarczyłyby dowodów, że górnej granicy nie można poprawić (modulo jakaś forma wykładniczej hipotezy czasowej).

András Salamon
źródło

tylko stycznie spokrewnione, ale istnieje najnowszy artykuł ECCC, który formułuje „prawie 2-SAT” w inny sposób i wykazuje silną twardość: eccc.hpi-web.de/report/2013/159

Sasho Nikolov

8

Ok, rozumiem. Odpowiedź brzmi nie. Można to rozwiązać w czasie wieloczasowym. Dla każdej klauzuli 3 lub więcej terminów wybierz literał i ustaw go jako prawdziwy. Następnie rozwiąż pozostały problem 2-sat. Jeśli ktoś oferuje rozwiązanie, to jest to rozwiązanie ogólnego problemu. Ponieważ liczba klauzul 3-lub więcej-terminowych jest stała (powiedzmy c), to jeśli wszystkie takie klauzule mają rozmiar <= m, to działa to w O (m ^ (c) * n). O (m ^ c) dla przejścia przez każdy możliwy wybór, czasy O (n) dla rozwiązania pozostałego problemu 2-sat.

dspyz
źródło

m

$m$

Jest tak, ponieważ m jest domyślnie ograniczone przez liczbę atomów. Oczywiście klauzula nie może zawierać więcej literałów niż atomów w tym problemie. Być może powinienem był wyjaśnić m <= n

dspyz

Czy Almost-2-SAT NP-hard jest trudny?

Odpowiedzi: