Twierdzenie Ladnera vs. Twierdzenie Schaefera

Czytając artykuł „Czy nadszedł czas, aby zadeklarować zwycięstwo w liczeniu złożoności?” na blogu „Godel's Lost Letter and P = NP” wspominali o dychotomii CSP. Po kilku linkach, googlowaniu i wikipedii natknąłem się na twierdzenie Ladnera :

Twierdzenie Ladnera: jeśli , wówczas występują problemy w , które nie są -kompletne.${\bf P} \ne {\bf NP}$${\bf NP} \setminus {\bf P}$${\bf NP}$

i do twierdzenia Schaefera :

Twierdzenie dychotomii Schaefera: Dla każdego języka ograniczeń ponad , jeśli to Schaefer, to jest rozwiązaniem wielomianowym. W przeciwnym razie ma -kompletny.$\ \Gamma$$\{0, 1\}$$\ \Gamma$${\bf CSP}(\Gamma)$${\bf CSP}(\Gamma)$${\bf NP}$

Czytam to, co oznacza, że ​​według Ladnera istnieją problemy, które nie są ani ani -kompletne, ale Schaefer ma problemy i -kompletne tylko.${\bf P}$${\bf NP}$${\bf P}$${\bf NP}$

czego mi brakuje? Dlaczego te dwa wyniki nie są ze sobą sprzeczne?

Wziąłem stąd skróconą wersję powyższych twierdzeń twierdzeń . W swojej sekcji „Uwagi końcowe” mówi: „Zatem jeśli problem dotyczy ale nie jest on to nie można go sformułować jako CSP” .${\bf NP} \setminus {\bf P}$${\bf NP}$

Czy to oznacza, że w problemach brakuje niektórych wystąpień z ? Jak to możliwe?${\bf SAT}$${\bf NP}$

Jak stwierdza Massimo Lauria, problemy z formą CSP ( ) są raczej szczególne. Więc nie ma sprzeczności.$\Gamma$

Satysfakcji ograniczenia przykład problem może być przedstawiony w postaci pary struktur relacyjne i , i trzeba podjąć decyzję, czy istnieje relacyjnej struktury homomorfizm ze źródła do docelowej . $(S,T)$$S$$T$$S$$T$

CSP ( ) jest szczególnym rodzajem problemu satysfakcji z ograniczeń. Składa się ze wszystkich par struktur relacyjnych, które są budowane przy użyciu tylko relacji w docelowej strukturze relacyjnej: CSP ( ) = . Twierdzenie Schaefera mówi, że gdy zawiera tylko relacje ponad , wówczas CSP ( ) jest albo NP-zupełny albo w P, ale nic nie mówi o innych kolekcjach instancji CSP.$\Gamma$$\Gamma$$\Gamma$$\{(S,T) \mid \text{all relations of } T \text{ are from } \Gamma\}$$\Gamma$$\{0,1\}$$\Gamma$

Jako skrajny przykład można zacząć od jakiegoś CSP ( ), który jest NP-complete i „wydmuchać dziury” w języku. (Ladner zrobił to z SAT na dowód swojego twierdzenia.) Wynikiem jest podzbiór zawierający tylko niektóre instancje, i już nie w postaci CSP ( ) dla żadnego . Powtórzenie konstrukcji daje nieskończoną hierarchię języków o malejącej twardości, przy założeniu P ≠ NP.$\Gamma$$\Gamma'$$\Gamma'$

Musisz zrozumieć, że problemy z mają strukturę, której nie mają ogólne problemy z . Dam ci prosty przykład. Niech . Ten język umożliwia wyrażanie tylko równości i nierówności między dwiema zmiennymi. Oczywiście każdy taki zestaw ograniczeń można rozwiązać w czasie wielomianowym.$\mathsf{CSP}$$\mathbf{SAT}$$\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$

Podam dwa argumenty, aby wyjaśnić związek między a klauzulami. Zauważ, że wszystko, co następuje, zakłada .$\mathsf{CSP}$$\mathbf{P}\not=\mathbf{NP}$

Po pierwsze : ograniczenia mają stałą liczbę zmiennych, podczas gdy kodowanie problemów pośrednich może wymagać dużych klauzul. Niekoniecznie jest to problemem, gdy tak duże ograniczenia można wyrazić jako połączenie małych z wykorzystaniem zmiennych pomocniczych. Niestety nie zawsze tak jest w przypadku ogólnego .$\Gamma$

Załóżmy, że zawiera po prostu pięciu zmiennych. Oczywiście można wyrazić mniej zmiennych, powtarzając dane wejściowe. Nie możesz wyrazić większego ponieważ sposób na zrobienie tego przy użyciu zmiennych rozszerzeń wymaga rozróżnienia literałów dodatnich i ujemnych. reprezentuje relacje na zmiennych , a nie na literałach . Rzeczywiście, gdy myślisz o 3- jako , potrzebujesz aby zawierać cztery relacje rozłączności z pewnymi zanegowanymi danymi wejściowymi (od zera do trzech).$\Gamma$$\mathsf{OR}$$\mathsf{OR}$$\mathsf{OR}$$\Gamma$$\mathbf{SAT}$$\mathsf{CSP}$$\Gamma$

Po drugie : każda relacja w może być wyrażona jako seria zdań zawierających (powiedzmy) trzy literały. Każde ograniczenie musi być całą serią takich klauzul. W przykładzie z ograniczeniami równości / nierówności nie można mieć pliku binarnego (tj. Relacji ) bez wymuszenia binarnego negacji (tj. Relacji ) na tych samych zmiennych.$\Gamma$$\mathsf{AND}$${(1,1)}$$\mathsf{OR}$${(0,0)}$

Mam nadzieję, że to pokazuje, że wystąpienia uzyskane z mają bardzo osobliwą strukturę, która jest wymuszona przez naturę . Jeśli struktura jest zbyt ciasna, nie możesz wyrazić trudnych problemów. $\mathbf{SAT}$$\mathsf{CSP}$$\Gamma$

Następstwem twierdzenia Schaefera jest to, że ilekroć wymusza strukturę wystarczająco luźną, aby wyrazić problemy decyzyjne z , wtedy ta sama pozwala na wystarczającą swobodę wyrażania ogólnych wystąpień 3- .$\Gamma$$\mathbf{NP\backslash P}$$\Gamma$$\mathsf{SAT}$