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

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

Aby sformalizować to dokładniej, pozwól

Φ (x) = \land_{ja}^{n} {do}_{ja},

$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$

gdzie $\mathbf{x} = (x_1,\dots,x_m)$ a każda klauzula $C_i$ ma postać $(x_i \oplus x_j)$ lub $(x_i \oplus \neg x_j)$ .

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

$\text{MAX-2-XOR-SAT}$ problemem jest znalezienie zadanie do $\mathbf{x}$ , który maksymalizuje liczbę klauzul, które są spełnione. Problem $\text{MIN-2-XOR-SAT}$ polega na znalezieniu przypisania do $\mathbf{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:

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 . $({x_i}\oplus x_j)$

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 $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4)$

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 we wzorze MONOTONE-MAX-2XOR-SAT, zobacz to . A maksymalny problem dwustronnego subgrafu jest równoważny maksymalnemu cięciu $k$ $k$

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łę $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5)$

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

— rotia
źródło

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 , utwórz krawędź między dwoma wierzchołkami, jeśli istnieje między nimi relacja XOR. Aby stwierdzenie było prawdziwe, powinno spełniać . 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_i\oplus x_j)$ $x_i$ $x_i\oplus x_j$ $x_i\neq x_j$ $x_i\oplus x_j$ 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

(x_{i} \oplus x_{j})

$(x_i \oplus x_j)$

(x_{k} \oplus \neg x_{l})

$(x_k \oplus \neg x_l)$

k, l

$k,l$

(x_{k} \oplus \neg x_{l})

$(x_k \oplus \neg x_l)$

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

x_{i} \oplus x_{k}

$x_i\oplus x_k$

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