Mengapa teorema Schaefer tidak membuktikan bahwa P = NP?

12

Ini mungkin pertanyaan bodoh, tapi saya tidak mengerti. Dalam pertanyaan lain mereka datang dengan teorema dikotomi Schaefer . Bagi saya sepertinya ini membuktikan bahwa setiap masalah CSP adalah dalam P atau NP-complete, tetapi tidak di antaranya. Karena setiap masalah NP dapat diubah dalam waktu Polinomial menjadi CSP (karena CSP adalah NP-complete), mengapa ini tidak membuktikan bahwa tidak ada ruang antara P dan NP-Complete dan sehingga P = NP?

Sebagai contoh, pikiranku seperti, faktorisasi bilangan bulat dapat ditulis ulang sebagai masalah kepuasan, jadi dengan menggunakan teorema Schaefer itu harus dalam P atau NP-lengkap tetapi tidak di antaranya (bahkan jika kita tidak dapat menemukan yang mana itu).

Cara berbeda untuk melihat seluruh pertanyaan: Mengapa kita tidak dapat menggunakan teorema Schaefer untuk memutuskan apakah faktorisasi bilangan bulat dalam P atau dalam NP-complete?


EDIT: sebagai tanggapan atas jawaban David Richerby (terlalu panjang untuk komentar):

Menarik, tapi saya belum sepenuhnya mengerti. Ketika mendefinisikan seperangkat hubungan gamma saat menggunakan teorema Schaefer, kita dapat memberlakukan batasan padanya. Sebagai contoh, kami dapat membatasi gamma untuk hanya menggunakan hubungan arity 2 (maka masalahnya ada di P). Pembatasan apa yang dapat kita berikan pada gamma?

Mengapa kita tidak dapat memaksakan pembatasan seperti itu sehingga semua instance CSP (gamma) persis sama dengan (isomorfik?) L? Misalnya, ketika menerjemahkan faktorisasi Integer untuk angka yang tidak rata, salah satu dari dua pembagi adalah biner yang direpresentasikan sebagai xn .. x3 x2 1. Sekarang, saya ingin angka ini lebih besar dari 1. Jadi, saya memiliki hubungan (xn atau .. atau x3 atau x2). Jadi saya katakan bahwa gamma dapat memiliki atau-hubungan arity n-1. Tapi saya tidak ingin bahwa atau-relasi digunakan untuk memasukkan contoh lain selain L dalam bahasa, jadi saya lebih jauh memaksakan bahwa x2..xn dalam atau-relasi tidak diperbolehkan memiliki negasi. Tentu saja, saya juga perlu memaksakan batasan bahwa hanya variabel tertentu yang digunakan di sana.

Apakah tidak mungkin dengan cara ini membiarkan CSP (gamma) menjadi isomorfik menjadi faktorisasi bilangan bulat? Pertanyaan utamanya adalah: batasan apa yang mungkin kita berikan pada gamma?

EDIT 2: sebagai jawaban atas jawaban Yuval Filmus.

Saya mengerti jawaban Anda dan tampaknya benar, meskipun hampir sama dengan jawaban David. Sebagai contoh, kita dapat mengurangi faktorisasi menjadi 3-sat dan kemudian menyimpulkan bahwa faktorisasi adalah NP lengkap, yang salah karena 3-sat memiliki contoh lain yang mungkin bukan faktorisasi.

Bagian yang saya tidak mengerti, adalah ketika sebuah instance (non-) sewenang-wenang. Sebagai contoh, 2-SAT juga tampak tidak arbitrer bagi saya, karena hanya klausa arity 2 yang diizinkan (walaupun saya harus mengakui bahwa buktinya masih berlaku karena itu adalah batas atas dan dalam hal ini batas atas adalah P).

Mungkin contoh yang lebih baik adalah NP-kelengkapan: pertanyaan terkait di atas. Satu penjawab memberikan bukti Schaefer lengkap. Tapi saya memaksakan pembatasan non-sepele pada input (klausa 2-SAT diizinkan dan xor-klausa, tetapi tidak ada yang lain). Tentu saja, buktinya masih berlaku karena masalah CSP yang dipertimbangkan dalam buktinya persis sama dengan yang asli.

Bagian yang saya tidak mengerti adalah mengapa kita tidak dapat melakukan hal yang sama untuk faktorisasi? Tentu saja tidak ada gunanya menguranginya menjadi 3-SAT, tetapi izinkan saya untuk memberikan contoh CSP yang memfaktorkan angka dan hanya memfaktorkan angka (4 bit). (lewati ke END-OF-SKIP jika Anda yakin ini mungkin).

Contoh faktorisasi.

MEMASUKKAN:

n4n3n2n1
m4m3m2m1

Sekarang, mari kita ubah ini menjadi instance CSP


n5..n1m5..m1


d4d3d2d1
e4e3e2e1

hubungan:

e4e3e2

(d4¬m4)(d4=m4d3¬m3)(d4=m4d3=m3d2¬m2)(d4=m4d3=m3d2=m2d1¬m1)

d1e1=n1
(d1e2)(d2e1)=n2
n3=...;n4=...

AKHIR-SKIP

Intinya adalah, ketika menerapkan teorema Schaefer, kita hanya harus mempertimbangkan CSP tersebut . (Sama seperti untuk 2-SAT kami hanya mempertimbangkan CSP dengan arity 2). Ketika melakukan itu, salah satu dari enam polimorfisme itu berlaku, atau tidak (simpan beberapa kebiasaan dalam teori himpunan). Dalam kedua kasus tersebut, faktorisasi bukanlah NP-intermediate.

Ini juga dapat dilakukan untuk 3-SAT. Kemudian, kita hanya harus mempertimbangkan (menggunakan reduksi) instance 3-SAT yang mewakili instance faktorisasi (yang bukan lagi 3-SAT).

Di mana saya salah?

Albert Hendriks
sumber
1
Saya sangat menyarankan agar Anda membaca formulasi yang tepat dari teorema dikotomi Schaefer. Tidak benar bahwa Anda "dapat mengenakan batasan pada [set hubungan]". Teorema dikotomi Schaefer tidak mencakup kasus ini. Wikipedia kadang-kadang bisa tidak akurat dan membingungkan, jadi saya sarankan Anda menemukan catatan kuliah sebagai gantinya, atau mungkin bahkan melihat makalah yang relevan.
Yuval Filmus
Saya tidak melihat komentar Anda sebelum mengedit jawaban saya. Mungkin tidak diperbolehkan untuk memberlakukan batasan pada himpunan relasi, tetapi menurut saya seolah-olah Anda seharusnya tidak mempertimbangkan hubungan yang tidak cocok dengan batasan saat menerapkan teorema Schaefer. Sama seperti dengan 2-SAT, Anda tidak menganggap hubungan yang tidak cocok dengan "pembatasan" yang setiap klausa harus memiliki 2 literal.
Albert Hendriks
2
ΓCSP(Γ)ΓCSP(Γ)
3
CSP(Γ)
1
tetapi apakah ada yang tahu buku teks bagus atau perawatan modern dari dikotomi Schaeffer thm?
vzn

Jawaban:

10

LΓΓLLΓLΓ

David Richerby
sumber
Menarik. Saya mengedit pertanyaan saya sebagai jawaban atas jawaban Anda.
Albert Hendriks
ΓΓΓ
Saya mungkin salah, tetapi saya akan mengatakan bahwa input ke masalah faktorisasi Integer adalah sama dengan input ke CSP (gamma): setiap dua angka biner (angka yang akan difaktorkan dan nilai minimum salah satu pembagi) . Baik? Saya mengerti bagian bahwa jika Anda tidak melakukan transformasi dengan hati-hati, Anda berakhir dengan masalah lain.
Albert Hendriks
ΓΓ
12

ΓCSP(Γ)

ΓCSP(Γ)

Yuval Filmus
sumber
Terima kasih untuk balasan Anda. Saya mengedit pertanyaan saya (EDIT 2) sebagai jawaban atas jawaban Anda.
Albert Hendriks