Zastanawiam się, czy istnieje algorytm wielomianowy dla „2-SAT z relacjami XOR”. Zarówno 2-SAT, jak i XOR-SAT są w P, ale czy jest to kombinacja?
Przykładowe dane wejściowe:
Część 2-SAT:
(a or !b) and (b or c) and (b or d)
Część XOR:
(a xor b xor c xor 1) and (b xor c xor d)
Innymi słowy, wejściem jest następująca formuła boolowska:
Przykładowy wynik: Zadowalający: a = 1, b = 1, c = 0, d = 0.
Zarówno liczba klauzul 2-SAT, jak i liczba klauzul XOR na wejściu to , gdzie jest liczbą zmiennych boolowskich.n
np-complete
satisfiability
xor
2-sat
Albert Hendriks
źródło
źródło
Odpowiedzi:
Relacje 2-SAT-z-XOR można udowodnić jako NP-zupełne poprzez redukcję z 3-SAT. Dowolną klauzulę 3-SAT można przepisać w wyrażeniu relacji 2-SAT-z-XOR nie do spełnienia ( x 1 ∨ ¯ y ) ∧ ( y ⊕ x 2 ⊕ z ) ∧ ( ¯ z ∨ x 3 ) z y i z jako nowe zmienne.
źródło
Nie określiłeś arsencji swoich relacji XOR, ale tak jak w zwykłej redukcji SAT-do-3SAT, zawsze możesz ustalić, że ich arsenacja będzie wynosić co najwyżej 3. Teraz jesteś w dobrej sytuacji, aby zastosować twierdzenie dychotomii Schaefera , które będzie powiedzą ci, czy twój problem jest w P czy NP-complete (są to tylko dwie opcje). Jeśli okaże się, że jest to P, następnym krokiem może być Allender i in. , dzięki czemu dowiesz się, jak łatwy jest twój problem.
źródło
Według twierdzenia dychotomii Schaefera jest to NP-zupełne.
Teraz zastosuj twierdzenie dychotomii Schaefera w jego nowoczesnej formie . Sprawdź każdą z sześciu operacji, aby sprawdzić, czy jest to polimorfizm:
Wynika z tego, że ten problem jest NP-zupełny, nawet jeśli ograniczysz wszystkie klauzule XOR do maksymalnej długości 3.
źródło