MIN-2-XOR-SAT i MAX-2-XOR-SAT: czy są NP-twarde?

13

Jaka jest złożoność MIN-2-XOR-SAT i MAX-2-XOR-SAT ? Czy są w P? Czy są twarde NP?

Aby sformalizować to dokładniej, pozwól

Φ(x)=jandoja,

gdzie x=(x1,,xm) a każda klauzula Ci ma postać (xixj) lub (xi¬xj) .

Problem 2-XOR-SAT polega na znalezieniu przypisania do x które spełnia Φ . Ten problem występuje w P , ponieważ odpowiada układowi równań liniowych mod 2 .

MAX-2-XOR-SAT problemem jest znalezienie zadanie do x , który maksymalizuje liczbę klauzul, które są spełnione. Problem MIN-2-XOR-SAT polega na znalezieniu przypisania do x które minimalizuje liczbę spełnionych klauzul. Jakie są złożoności tych problemów?

Inspirowany przez Czy MIN lub MAX-True-2-XOR-SAT NP-hard?

DW
źródło

Odpowiedzi:

6

Przepraszamy za odpowiedź na stary post

Problem określania, czy instancja MONOTONE-2-XOR-SAT (wszystkie zdania są tego rodzaju ) jest zadowalająca, można sprowadzić do problemu określania, czy wykres jest dwustronny, zobacz to .(xixj)

Aby to zrobić, tworzymy wykres z węzłem dla każdego literału formuły i łączymy każdy literał z innym, jeśli są w tej samej klauzuli (krawędzie są klauzulami)G

Na przykład:

Jeśli mamy niezadowalającą formułę, którą jest (x1x2))(x1x3))(x2)x3))(x1x4)

Mamy taki wykres:

grafo no bipartito

to nie jest dwustronne

Istnieją trzy klauzule, które są zadowalające, dlatego musimy po prostu wyeliminować przewagę

Teraz możemy zredukować problem określania, czy możemy znaleźć maksymalny dwudzielny podsgraf z wierzchołkiem do problemu określania, czy możemy spełnić klauzule k we wzorze MONOTONE-MAX-2XOR-SAT, zobacz to . A maksymalny problem dwustronnego subgrafu jest równoważny maksymalnemu cięciukk

Aby dokonać redukcji, po prostu tworzymy nowy literał dla każdego wierzchołka i tworzymy klauzulę dla każdej krawędzi łączącej dwa literały

Na przykład:

Mamy ten wykres,

grafo no bipartito 2

Tworzymy następującą formułę (x1x2))(x1x4)(x2)x4)(x2)x3))(x4x5)(x3)x5)

Jeśli więc znajdziemy przypisanie spełniające klauzule , będzie to oznaczać, że istnieje dwustronny podsgraf o co najmniej k krawędziach.kk

rotia
źródło
1
Powinieneś wyraźnie powiedzieć, że implikacja: ponieważ MAX-CUT jest NP-twardy, redukcja do MAX-XORSAT oznacza, że ​​jest również NP-twarda.
Antymon
-1

Tam gdzie każda klauzula jest podana tylko jako , utwórz wierzchołek dla każdego literału x i , utwórz krawędź między dwoma wierzchołkami, jeśli istnieje między nimi relacja XOR. Aby stwierdzenie x ix j było prawdziwe, powinno spełniać x ix j . Teraz możemy zastosować problem kolorowania wierzchołków (żadne dwa wierzchołki połączone krawędzią nie mają tego samego koloru, mamy dodatkowe ograniczenie 2 kolorów tylko wtedy, gdy chcemy spełnić równanie). Klauzula x ix j(xixj)xixixjxixjxixj jest prawdziwe, jeśli odpowiednie wierzchołki mają przypisane różne kolory na wykresie.

Jeśli wszystkie wierzchołki wykresu można pokolorować za pomocą 2 kolorów i żaden z dwóch wierzchołków ze wspólnym udziałem krawędzi nie ma tego samego koloru, równanie jest zadowalające.

Ale wykres jest dwukolorowy, jeśli jest to wykres dwustronny. Określenie, czy wykres jest dwustronny, można wykonać w czasie wielomianowym. Dlatego problem występuje w P, ponieważ jeśli możemy ustalić w czasie wielomianowym, że wykres jest wykresem dwustronnym, to jest on do rozwiązania, w przeciwnym razie nie jest do rozwiązania.

jcod0
źródło
1
(xixj)(xk¬xl)k,l(xk¬xl)
2
To prowadzi mnie do poważniejszego problemu z twoją odpowiedzią. Problemem nie jest ustalenie, czy formuła jest zadowalająca; problemem jest określenie zadania, które spełnia maksymalną / minimalną liczbę klauzul. Twój algorytm sprawdza tylko, czy formuła jest zadowalająca. W ten sposób rozwiązuje 2-XOR-SAT, ale nie rozwiązuje MIN-2-XOR-SAT lub MAX-2-XOR-SAT - ale już wiedziałem, że 2-XOR-SAT jest w P, jak wyjaśniono w pytanie. Czy coś źle zrozumiałem?
DW
xjaxk
1
Ale wciąż nie rozumiem, w jaki sposób odnosi się to do mojego drugiego komentarza. Rozwiązałeś specjalny przypadek problemu, o który nie pytałem. Krótko mówiąc, ta odpowiedź nie odpowiada na pytanie, które zadałem.
DW