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?
2
Dobre pytanie. Myślę, że jedną intuicją jest to, że ograniczamy problemy do klasy, która ma ładne opisy.
—
Kaveh
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 ...
—
Joshua Grochow
Dychotomie występują, gdy język jest zbyt gruby, aby można go było dobrze rozróżnić.
—
András Salamon