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.
Di mana saya salah di sini? Saya curiga bahwa saya salah paham / salah menerapkan teorema Shaefer, tetapi saya tidak mengerti mengapa.
Jawaban:
sumber