Teorema Ladner vs. Teorema Schaefer

Saat membaca artikel "Apakah Saatnya Menyatakan Kemenangan dalam Menghitung Kompleksitas?" di blog "Surat Hilang Godel dan P = NP" , mereka menyebutkan dikotomi untuk CSP. Setelah beberapa link berikut, googling dan wikipeding, saya menemukan Teorema Ladner :

Teorema Ladner: Jika , maka ada masalah dalam yang bukan -lengkap.${\bf P} \ne {\bf NP}$${\bf NP} \setminus {\bf P}$${\bf NP}$

dan untuk teorema Schaefer :

Teorema Dikotomi Schaefer: Untuk setiap bahasa kendala over , jika adalah Schaefer maka adalah waktu polinomial yang dapat dipecahkan. Kalau tidak, adalah -lengkap.$\ \Gamma$$\{0, 1\}$$\ \Gamma$${\bf CSP}(\Gamma)$${\bf CSP}(\Gamma)$${\bf NP}$

Saya membaca ini berarti bahwa, oleh Ladner, ada masalah yang bukan atau -complete, tetapi menurut Schaefer, masalahnya adalah dan -complete hanya.${\bf P}$${\bf NP}$${\bf P}$${\bf NP}$

Apa yang saya lewatkan? Mengapa kedua hasil ini tidak saling bertentangan?

Saya mengambil versi ringkas dari pernyataan teorema di atas dari sini . Di bagian "Komentar Terakhir", ia berkata, "Jadi, jika ada masalah dalam tetapi tidak -lengkapi maka tidak dapat dirumuskan sebagai CSP" .${\bf NP} \setminus {\bf P}$${\bf NP}$

Apakah ini berarti masalah kehilangan beberapa kejadian yang ada di ? Bagaimana mungkin?${\bf SAT}$${\bf NP}$

Seperti yang dikatakan Massimo Lauria, masalah bentuk CSP ( ) agak istimewa. Jadi tidak ada kontradiksi.$\Gamma$

Setiap kepuasan kendala masalah misalnya dapat direpresentasikan sebagai pasangan struktur relasional dan , dan kita harus memutuskan apakah terdapat homomorfisma struktur relasional dari sumber dengan target . S T S $(S,T)$$S$$T$$S$$T$

CSP ( ) adalah jenis khusus masalah kepuasan kendala. Ini terdiri dari semua pasangan struktur relasional yang dibangun hanya menggunakan hubungan dari Γ dalam struktur relasional target: CSP ( Γ ) = { ( S , T ) ∣ semua relasi  T  berasal dari  Γ } . Teorema Schaefer mengatakan bahwa ketika Γ hanya berisi hubungan di atas { 0 , 1 } , maka CSP ( $\Gamma$$\Gamma$$\Gamma$$\{(S,T) \mid \text{all relations of } T \text{ are from } \Gamma\}$$\Gamma$$\{0,1\}$$\Gamma$) apakah NP-complete atau P, tetapi tidak mengatakan apa-apa tentang koleksi CSP lainnya.

Sebagai contoh ekstrem, seseorang dapat mulai dengan beberapa CSP ( ) yang NP-complete, dan "blow hole" dalam bahasa. (Ladner melakukan ini dengan SAT dalam pembuktian teorema-nya.) Hasilnya adalah himpunan bagian yang hanya berisi beberapa contoh, dan tidak lagi dalam bentuk CSP ( Γ ′ ) untuk Γ ′ apa pun . Mengulangi konstruksi menghasilkan hierarki bahasa yang tak terbatas dari penurunan kekerasan, dengan asumsi P ≠ NP.$\Gamma$$\Gamma'$$\Gamma'$

Anda perlu memahami bahwa masalah memiliki struktur yang generik S A T masalah tidak memiliki. Saya akan memberi Anda contoh sederhana. Biarkan Γ = { { ( 0 , 0 ) , ( 1 , 1 ) } , { ( 0 , 1 ) , ( 1 , 0 ) } $\mathsf{CSP}$$\mathbf{SAT}$$\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$. Bahasa ini sedemikian rupa sehingga Anda hanya bisa mengekspresikan persamaan dan ketidaksetaraan antara dua variabel. Jelas setiap batasan seperti itu dapat dipecahkan dalam waktu polinomial.

Saya akan memberikan dua argumen untuk memperjelas hubungan antara dan klausa. Perhatikan bahwa semua yang mengikuti mengasumsikan P ≠ N P .$\mathsf{CSP}$$\mathbf{P}\not=\mathbf{NP}$

Pertama : kendala memiliki sejumlah variabel tetap, sedangkan pengkodean masalah menengah mungkin membutuhkan klausa besar. Ini tidak selalu menjadi masalah ketika kendala besar seperti itu dapat dinyatakan sebagai gabungan dari yang kecil menggunakan variabel tambahan. Sayangnya ini tidak selalu berlaku untuk umum .$\Gamma$

Asumsikan hanya berisi O R dari lima variabel. Jelas Anda dapat mengekspresikan O R variabel yang lebih sedikit dengan mengulangi input. Anda tidak bisa mengungkapkan lebih besar O R karena cara untuk melakukannya dengan menggunakan variabel perpanjangan membutuhkan disjunctions literal positif dan negatif. Γ merepresentasikan hubungan pada variabel , bukan pada literal . Memang ketika Anda berpikir tentang 3- S A T sebagai C S P Anda perlu Γ mengandung empat hubungan disjungsi dengan beberapa input yang dinegasikan (dari nol hingga tiga).$\Gamma$$\mathsf{OR}$$\mathsf{OR}$$\mathsf{OR}$$\Gamma$$\mathbf{SAT}$$\mathsf{CSP}$$\Gamma$

Kedua : setiap relasi dalam dapat dinyatakan sebagai kumpulan klausa dengan (katakanlah) tiga literal. Setiap kendala harus merupakan keseluruhan kumpulan klausa tersebut. Dalam contoh dengan kendala kesetaraan / ketidaksetaraan Anda tidak dapat memiliki biner A N D (yaitu relasi ( 1 , 1 ) ) tanpa menegakkan biner yang dinegasikan O R (yaitu relasi ( 0 , 0 ) ) pada variabel yang sama.$\Gamma$$\mathsf{AND}$${(1,1)}$$\mathsf{OR}$${(0,0)}$

Saya harap ini menggambarkan kepada Anda bahwa contoh yang diperoleh dari C S P s memiliki struktur yang sangat aneh, yang diberlakukan oleh sifat Γ . Jika struktur terlalu ketat maka Anda tidak dapat mengungkapkan masalah sulit. $\mathbf{SAT}$$\mathsf{CSP}$$\Gamma$

Sebuah akibat wajar dari Teorema Schaefer adalah bahwa setiap kali memberlakukan struktur yang cukup longgar untuk mengekspresikan N P ∖ P masalah keputusan, maka hal yang sama Γ memungkinkan kebebasan yang cukup untuk mengekspresikan general 3- S A T instance.$\Gamma$$\mathbf{NP\backslash P}$$\Gamma$$\mathsf{SAT}$