Twierdzenie Ladnera vs. Twierdzenie Schaefera

27

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.PNPNPPNP

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. Γ{0,1} ΓCSP(Γ)CSP(Γ)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.PNPPNP

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” .NPPNP

Czy to oznacza, że w problemach brakuje niektórych wystąpień z ? Jak to możliwe?SATNP

użytkownik834
źródło
2
Czy nie ma w tym drobnego problemu, że trzeba uważać, jak definiuje się „język ograniczeń” i „problem”? Twierdzenie Schaefersa (o ile pamiętam) bierze pod uwagę tylko podane języki, przyjmując zamknięcie w połączeniu i zmienne podstawienie niektórych zbiorów S. Można jednak konstruować zestawy problemów związanych z ograniczeniami, które nie są przez to objęte, a więc mogą być możliwe do rozwiązania, ale nie Schaefer. Przypuszczalnie zbiór problemów, które konstruuje Ladner, po prostu nie da się zdefiniować w kategoriach zamknięcia w połączeniu i zmiennego podstawienia zbioru relacji.
MGwynne
1
Myślę, że należy zmienić ostatnie zdanie od instancja nie posiada (nietrywialne) złożoność, zestawy przypadkach mają złożoność. Oznaczałoby to, że żaden zestaw NPI instancji jest wyrażalny jako . SATCSP(Γ)
Kaveh

Odpowiedzi:

15

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

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)STST

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.ΓΓΓ{(S,T)all relations of T are from Γ}Γ{0,1}Γ

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.ΓΓΓ

András Salamon
źródło
23

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.CSPSATΓ={{(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 .CSPPNP

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 .Γ

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).ΓORORORΓSATCSPΓ

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.ΓAND(1,1)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. SATCSPΓ

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- .ΓNPPΓSAT

MassimoLauria
źródło
1
Aby dodać do doskonałej odpowiedzi MassimoLaurii; Nie ma sprzeczności. Przeczytaj ten artykuł w Wikipedii, który zawiera sekcję wyjaśniającą, w prostych słowach, związek między twierdzeniem Ladnera a twierdzeniem Schaefera.
Mohammad Al-Turkistany
Dla pewności rozumiem, mówisz, że ograniczona wersja 'S w twierdzeniu Schaefera albo nie jest w stanie zakodować dowolnej instancji 3- ani że instancji może rosnąć super-wielomianowo dla niektórych klas problemów 3- ? CSPSATCSP(Γ)SAT
user834 24.01.12
W twierdzeniu Schaefera pokazano kilka rodzajów indukujących wielomianowe algorytmy czasowe. Myślę (ale nie jestem pewien), że niektóre z nich nie mogą w ogóle wyrazić ogólnego 3 . Niemniej jednak za zbiór „klauzul 3 klaksonu”. Są one rozstrzygalne w czasie polime i każde obliczenie deterministyczne w czasie może być zakodowane jako formuła - o rozmiarze . Tak więc myślę, że można zakodować obliczenia długie wykładniczo za pomocą wykładniczo długiego (tj. Wykładniczo wiele zmiennych). Czy jest sens? ΓSATΓtHornSATpoly(t)CSP
MassimoLauria
Myślę, że właściwym sposobem jest powiedzenie, że dostawcy CSP w środowisku Schaefera nie mogą zakodować arbitralnego problemu NP (3-SAT jest w rzeczywistości kanonicznym problemem CSP). Zauważ, że jest to instrukcja warunkowa (chyba że P = NP).
Chandra Chekuri
@ChandraChekuri, przepraszam, że jestem tak gęsty, ale czy mówisz, że CSP w środowisku Schaefera nie mogą kodować arbitralnych instancji 3-SAT? CSP może ogólnie zakodować 3-SAT, ale ograniczona wersja CSP w środowisku Schaefera nie może?
user834 27.01.12