Apa yang dimakan teorema dikotomi?

Hal ini juga diketahui bahwa kelas-kelas tertentu dari NP -problems Memiliki dikotomi teorema, yang menjamin bahwa setiap tugas di kelas adalah baik NP -Lengkap atau di P . Hasil yang paling dikenal adalah teorema dikotomi Schaefer , bersama dengan sejumlah generalisasi.

Pemahaman saya adalah bahwa membuktikan teorema dikotomi ini tidaklah mudah. Saya bertanya-tanya, apakah ada penjelasan yang relatif singkat mengapa kelas tertentu memiliki teorema dikotomi, sementara yang lain tidak? Apa struktur masalah penting yang memungkinkan teorema ini menjadi mungkin? Atau mungkin tidak ada struktur yang dipahami dengan jelas, melainkan merupakan misteri dalam setiap kasus mengapa kelas tidak memiliki teorema dikotomi?

Untuk kasus teorema dikotomi Schaefer, secara informal, kekuatan ekspresif universal formula CNF Boolean yang dibangun dari hubungan logis non-Schaefer ada di belakang dikotomi. Setiap hubungan logis dapat didefinisikan oleh rumus tersebut menggunakan quantifier eksistensial. Ini dinyatakan secara formal dalam teorema keterbukaan Schaefer (Teorema 2.5).