Twierdzenie Schaefera o dychotomii

W teorii złożoności obliczeniowej , gałęzi informatyki , twierdzenie Schaefera o dychotomii określa warunki konieczne i wystarczające, w których skończony zbiór S relacji w domenie boolowskiej daje problemy wielomianowe lub NP-zupełne , gdy relacje S są używane do ograniczenia niektórych zmiennych zdaniowych . Nazywa się to twierdzeniem o dychotomii , ponieważ złożoność problemu zdefiniowanego przez S jest w P lub NP-zupełne, w przeciwieństwie do jednej z klas o pośredniej złożoności , o której wiadomo, że istnieje (zakładając P ≠ NP ) na podstawie twierdzenia Ladnera .

Szczególne przypadki twierdzenia o dychotomii Schaefera obejmują NP-zupełność SAT ( problem spełnialności Boole'a ) i jego dwa popularne warianty 1-w-3 SAT i nie wszystkie równe 3SAT (często oznaczane przez NAE-3SAT). W rzeczywistości dla tych dwóch wariantów SAT twierdzenie Schaefera o dychotomii pokazuje, że ich wersje monotoniczne (gdzie negacje zmiennych nie są dozwolone) są również NP-zupełne.

Oryginalna prezentacja

Schaefer definiuje problem decyzyjny , który nazywa uogólnionym problemem spełnialności dla S (oznaczonym przez SAT ( S )), gdzie ${\ Displaystyle S = \ {R_ {1}, \ ldots, R_{m}\}}$ jest skończonym zbiorem relacji nad zmiennymi zdaniowymi. Przykładem problemu jest S -formuła, czyli koniunkcja więzów postaci ${\ Displaystyle R_ {j} (x_ {i_ {1}}, \ ldots, x_ {i_ {n}})}$ gdzie ${\ Displaystyle R_ {j} \ w S}$ i x $j}}}$ są zmiennymi zdaniowymi. Problem polega na ustaleniu, czy dana formuła jest spełnialna, czyli czy zmiennym można przypisać takie wartości, aby spełniały wszystkie ograniczenia wynikające z relacji z S .

Schaefer identyfikuje sześć klas zbiorów relacji boolowskich, dla których SAT( S ) jest w P i dowodzi, że wszystkie inne zbiory relacji generują problem NP-zupełny. Skończony zbiór relacji S w domenie logicznej definiuje problem spełnialności obliczalnej w czasie wielomianowym, jeśli spełniony jest jeden z następujących warunków:

wszystkie relacje, które nie są stale fałszywe, są prawdziwe, gdy wszystkie jej argumenty są prawdziwe;
wszystkie relacje, które nie są stale fałszywe, są prawdziwe, gdy wszystkie jej argumenty są fałszywe;
wszystkie relacje są równoważne koniunkcji zdań binarnych;
wszystkie relacje są równoważne koniunkcji klauzul Horna ;
wszystkie relacje są równoważne koniunkcji klauzul dual-Horn;
wszystkie relacje są równoważne koniunkcji formuł afinicznych.

W przeciwnym razie problem SAT( S ) jest NP-zupełny.

Nowoczesna prezentacja

Nowoczesna, usprawniona prezentacja twierdzenia Schaefera została przedstawiona w artykule wyjaśniającym autorstwa Hubiego Chena. We współczesnych terminach problem SAT( S ) jest postrzegany jako problem spełnienia ograniczeń w domenie boolowskiej . W tym obszarze standardem jest oznaczanie zbioru relacji przez Γ, a problemu decyzyjnego zdefiniowanego przez Γ jako CSP(Γ).

To nowoczesne rozumienie wykorzystuje algebrę, w szczególności algebrę uniwersalną . W przypadku twierdzenia Schaefera o dychotomii najważniejszym pojęciem w algebrze uniwersalnej jest polimorfizm. Operacja ${\ displaystyle f: D ^ {m} \ do re}$ jest polimorfizmem relacji ${\ displaystyle R \ subseteq D ^ {k}}$ , jeśli dla dowolnego wyboru m krotek ${\ Displaystyle (t_ {11}, \ kropka, t_ {1k}), \ kropka, (t_ {m1}, \ kropka, t_ {mk})}$ z R , to utrzymuje, że krotka uzyskana z tych m krotek poprzez zastosowanie f współrzędnych, tj. ${\ Displaystyle (f (t_ {11}, \ kropka, t_ {m1}), \ kropka, f (t_ {1k}, \ kropka, t_ {mk}})}$ , jest w r . Oznacza to, że operacja f jest polimorfizmem R , jeśli R jest domknięte pod f : zastosowanie f do dowolnych krotek w R daje kolejną krotkę wewnątrz R. Mówimy, że zbiór relacji Γ ma polimorfizm f , jeśli każda relacja w Γ ma f jako polimorfizm. Definicja ta pozwala na algebraiczne sformułowanie twierdzenia Schaefera o dychotomii.

Niech Γ będzie skończonym językiem z ograniczeniami w domenie boolowskiej. Problem CSP (Γ) jest rozstrzygalny w czasie wielomianowym, jeśli Γ ma jedną z następujących sześciu operacji jako polimorfizm:

stała operacja jednoargumentowa 0;
stała operacja jednoargumentowa 1;
operacja binarna AND ∧;
binarna operacja OR ∨;
trójskładnikowej większości ${\ Displaystyle \ nazwa operatora {Większość} (x, y, z) = (x \ klin y) \ vee (x \ klin z) \ vee (y \ klin z);}$
potrójna operacja mniejszościowa ${\ Displaystyle \ nazwa operatora {mniejszość} (x, y, z) = x \ oplus y \ oplus z.}$

W przeciwnym razie problem CSP(Γ) jest NP-zupełny.

W tym sformułowaniu łatwo jest sprawdzić, czy spełniony jest którykolwiek z warunków wykonalności.

Właściwości polimorfizmów

Biorąc pod uwagę zbiór Γ relacji, istnieje zaskakująco ścisły związek między jego polimorfizmami a złożonością obliczeniową CSP(Γ).

Relacja R nazywana jest prymitywną pozytywną definiowalną lub krótką pp-definiowalną ze zbioru Γ relacji, jeśli R ( v ₁ , ... , v _k ) ⇔ ∃ x ₁ ... x _m . C zachodzi dla pewnej koniunkcji C ograniczeń z Γ i równań nad zmiennymi { v ₁ ,..., v _k , x ₁ ,..., x _m }. Na przykład, jeśli Γ składa się z trójskładnikowej relacji nae ( x , y , z ) utrzymującej, że x , y , z nie wszystkie są równe, a R ( x , y , z ) to x ∨ y ∨ z , to R może być pp-określony przez R ( x , y , z ) ⇔ ∃ za . nie (0, x , za ) ∧ nae ( y , z , ¬ a ); ta redukcja została wykorzystana do udowodnienia, że NAE-3SAT jest NP-zupełny. Zbiór wszystkich relacji definiowalnych przez pp z Γ jest oznaczony przez ≪Γ≫. Jeśli Γ' ⊆ ≪Γ≫ dla pewnych skończonych zbiorów ograniczeń Γ i Γ', to CSP(Γ') redukuje się do CSP(Γ).

Biorąc pod uwagę zbiór Γ relacji, Pol (Γ) oznacza zbiór polimorfizmów Γ. I odwrotnie, jeśli O jest zbiorem operacji, to Inv ( O ) oznacza zbiór relacji, w których wszystkie operacje w O są polimorfizmem. Pol i Inv wspólnie budują połączenie Galois . Dla dowolnego skończonego zbioru Γ relacji w dziedzinie skończonej zachodzi ≪Γ≫ = Inv(Pol(Γ)), to znaczy zbiór relacji pp-definiowalnych z Γ można wyprowadzić z polimorfizmów Γ. Ponadto, jeśli Pol (Γ) ⊆ Pol (Γ') dla dwóch skończonych zbiorów relacji Γ i Γ', to Γ' ⊆ ≪Γ≫ i CSP(Γ') redukuje się do CSP(Γ). W konsekwencji dwa zbiory relacji mające te same polimorfizmy prowadzą do tej samej złożoności obliczeniowej.

Uogólnienia

Analiza została później dopracowana: CSP(Γ) jest albo rozwiązywalne w co-NLOGTIME, L-complete , NL-complete , ⊕L-complete, P-complete lub NP-complete i biorąc pod uwagę Γ, można zdecydować w czasie wielomianowym który z tych przypadków zachodzi.

Twierdzenie Schaefera o dychotomii zostało ostatnio uogólnione na większą klasę relacji.

Powiązana praca

Jeśli problemem jest policzenie liczby rozwiązań, co jest oznaczone przez #CSP(Γ), to podobny wynik uzyskany przez Creignou i Hermanna jest spełniony. Niech Γ będzie skończonym językiem z ograniczeniami w domenie boolowskiej. Problem #CSP(Γ) jest obliczalny w czasie wielomianowym, jeśli Γ ma operację Mal'tseva jako polimorfizm. W przeciwnym razie problem #CSP(Γ) jest #P-zupełny . Operacja Malcewa m jest operacją trójskładnikową spełniającą ${\ Displaystyle m (x, y, y) = m (y, y, x) = x.}$ Przykładem operacji Mal'tseva jest operacja mniejszości podana we współczesnym, algebraicznym sformułowaniu powyższego twierdzenia Schaefera o dychotomii. Zatem, gdy Γ ma operację Mniejszości jako polimorfizm, możliwe jest nie tylko wyznaczenie CSP(Γ) w czasie wielomianowym, ale także obliczenie #CSP(Γ) w czasie wielomianowym. Istnieją w sumie 4 operacje Mal'tseva na zmiennych boolowskich, określone przez wartości ${\ Displaystyle m (T, F,$ } ${\ Displaystyle m (F, T, F)}$ . Przykład mniej symetrycznego podaje ${\ Displaystyle m (x, y, z) = (x \ klin z)\vee (\neg y\klin (x\vee z))}$ . W innych domenach, takich jak grupy, przykłady operacji Mal'tseva obejmują ${\ displaystyle xy + z}$ i ${\ displaystyle xy ^ {-1} z.}$

W przypadku większych domen, nawet dla dziedziny o rozmiarze trzy, istnienie polimorfizmu Mal'tseva dla Γ nie jest już wystarczającym warunkiem podatności #CSP(Γ). Jednak brak polimorfizmu Mal'tseva dla Γ nadal implikuje #P-twardość #CSP(Γ).

Zobacz też

Maks/min Twierdzenia klasyfikacyjne CSP/Jedynki , podobny zestaw ograniczeń dla problemów optymalizacyjnych