Mengapa Teorema Shaefer dan Mahaney tidak menyiratkan P = NP?

14

Saya yakin seseorang telah memikirkan hal ini sebelum atau segera menolaknya, tetapi mengapa teori dikotomi Schaefer bersama dengan teorema Mahaney tentang set jarang tidak menyiratkan P = NP?

Inilah alasan saya: Buat bahasa yang sama dengan SAT berpotongan dengan set jarang decidable terbatas. Maka L juga harus jarang. Karena L itu tidak sepele, affine, 2-sat, atau Horn-sat, oleh teorema Shaefer itu harus NP-lengkap. Tapi kemudian kita memiliki satu set NP-lengkap yang jarang jadi oleh teorema Mahaney, P = NP.LLL

Di mana saya salah di sini? Saya curiga bahwa saya salah paham / salah menerapkan teorema Shaefer, tetapi saya tidak mengerti mengapa.

Ari
sumber
1
Terkait erat: cs.stackexchange.com/q/42544/755 (baca jawaban sebelum mencoba memahami semua detail pertanyaan; jawabannya relatif mandiri)
DW
bertanya-tanya tentang ini sendiri sebelum banyak untuk bertanya! masalahnya adalah bahwa schaefers thm sebenarnya tidak menyatakan bahwa tidak ada bahasa antara "antara" P / NP, itu lebih halus. juga, coba pelajari kelas NPI, alias NP menengah, ada banyak referensi tentang Theoretical Computer Science . banyak masalah utama adalah "di" NPI, dua teratas / terkenal adalah anjak piutang dan grafik isomorfisme.
vzn
Singkatnya Shaefer thm terdengar seperti thm tentang SAT tetapi sebenarnya tentang bahasa sempit yang terkait dengan SAT yang ternyata bukan NP keras atau NP lengkap ....? telah lama mencari presentasi tingkat "buku teks sarjana" dari Shaefer thm ....
vzn

Jawaban:

13

SAT(S)CSP(Γ)L.

Yuval Filmus
sumber
keren tapi apa sebenarnya SAT (S)?
tlg selesaikan
Ini dijelaskan dengan sangat jelas di halaman Wikipedia tentang teorema Schaefer, dari mana saya menyalin notasi ini.
Yuval Filmus
1
tapi bagaimanapun tetap berpikir ini semua bisa dijelaskan lebih baik. "Schaefer mendefinisikan masalah keputusan yang dia sebut masalah Generalized Satisfiability". tapi ternyata tidak begitu digeneralisasi kalau begitu ....? misalnya mengapa bahasa yang ia pelajari penting, dan tidak dibuat-buat? Apakah ini digunakan di tempat lain di CS selain makalahnya? apa implikasi yang lebih besar dari teorema ini, apakah ada atau apakah itu merupakan keingintahuan terisolasi yang tampaknya tidak mengarah ke mana pun? mungkinkah itu bisa digunakan entah bagaimana dalam serangan P vs NP atau tidak? dll
vzn