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.
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.
Czytam to, co oznacza, że według Ladnera istnieją problemy, które nie są ani ani -kompletne, ale Schaefer ma problemy i -kompletne tylko.
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” .
Czy to oznacza, że w problemach brakuje niektórych wystąpień z ? Jak to możliwe?
źródło
Odpowiedzi:
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) 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.Γ Γ Γ {(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.Γ Γ′ Γ′
źródło
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.CSP SAT Γ={{(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 .CSP P≠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 .Γ
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).Γ OR OR OR Γ SAT CSP Γ
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.SAT CSP Γ
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- .Γ NP∖P Γ SAT
źródło