Na czym polegają twierdzenia o dychotomii?

10

Powszechnie wiadomo, że pewne klasy NP -Problemy Have dychotomia twierdzeń, które gwarantują, że każde zadanie w klasie jest albo NP -Complete lub jest w P . Najbardziej znanym takim wynikiem jest twierdzenie Schaefera o dychotomii wraz z szeregiem uogólnień.

Rozumiem, że udowodnienie tych twierdzeń o dychotomii nie jest naprawdę łatwe. Zastanawiam się, czy istnieje jakieś stosunkowo krótkie wyjaśnienie, dlaczego niektóre klasy mają twierdzenia o dychotomii, a inne nie? Jaka jest zasadnicza struktura problemu, która umożliwia te twierdzenia? A może nie ma tak jasno rozumianej struktury, a raczej jest tajemnicą w każdym przypadku, dlaczego klasa ma lub nie ma twierdzenia o dychotomii?

cc.complexity-theory np descriptive-complexity Andras Farago
źródło
2
Dobre pytanie. Myślę, że jedną intuicją jest to, że ograniczamy problemy do klasy, która ma ładne opisy.
Kaveh
5
To nie jest odpowiedź, ale być może wskazuje gdzie potęga odpowiedź (nie) być: jeśli klasa problemów jest wystarczająco duży, aby zawierać wszystkie (lub nawet tylko konkretny podzbiór niego), a następnie zastosuje Ladner Twierdzenie i nie będzie dychotomii. Więc klasa z dychotomią musi przynajmniej mieć wystarczającą strukturę, aby uniknąć Ladnera ...N.P.
Joshua Grochow
1
Dychotomie występują, gdy język jest zbyt gruby, aby można go było dobrze rozróżnić.
András Salamon

Odpowiedzi:

2

W przypadku twierdzenia dychotomii Schaefera nieoficjalnie za dychotomią stoi uniwersalna moc ekspresyjna boolowskich formuł CNF zbudowanych na podstawie relacji logicznych innych niż Schaefer. Każda relacja logiczna jest definiowana przez taką formułę przy użyciu kwantyfikatora egzystencjalnego. Jest to formalnie stwierdzone w twierdzeniu Schaefera o wyrazistości (Twierdzenie 2.5).

Mohammad Al-Turkistany
źródło