Pertimbangkan masalah 3-SAT pada n variabel. Jumlah klausa berbeda yang mungkin adalah:
Jumlah kasus masalah adalah jumlah semua himpunan bagian dari himpunan mungkin klausa: . Secara sepele, untuk setiap , ada setidaknya satu instance yang memuaskan dan satu instance tidak memuaskan. Apakah mungkin untuk menghitung, atau setidaknya memperkirakan, jumlah instance yang memuaskan untuk setiap n yang diberikan? n ≥ 3
cc.complexity-theory
sat
Antonio Valerio Miceli-Barone
sumber
sumber
Jawaban:
Sejarah panjang kerja pada transisi fase dalam SAT telah menunjukkan bahwa untuk setiap tetap , ada ambang batas yang ditentukan oleh rasio jumlah klausa dengan yang menentukan kepuasan. Secara kasar, jika rasionya kurang dari 4,2, maka dengan probabilitas yang luar biasa contohnya memuaskan (dan karenanya sebagian besar dari jumlah instance dengan banyak klausa dan variabel ini memuaskan). Jika rasio sedikit di atas 4.2, maka kebalikannya memegang - sebagian besar contoh tidak memuaskan.nn n
Referensi terlalu banyak untuk dikutip di sini: satu sumber informasi adalah buku karya Mezard dan Montanari . Jika ada yang punya sumber survei dll tentang topik ini, mereka dapat mempostingnya di komentar atau mengedit jawaban ini (saya akan membuatnya menjadi CW)
Referensi:
- Survei Achlioptas
- Di mana masalah yang benar-benar sulit
- Memperbaiki transisi fase dalam pencarian kombinatorial
sumber
Di satu sisi, sebagian besar contoh tidak akan memuaskan, seperti yang dikatakan dalam komentar Suresh. (Faktanya, saya kira jika Anda mengambil satu contoh secara seragam secara acak, Anda seharusnya sudah memiliki kemungkinan yang baik untuk memasukkan semua delapan negasi sebagai klausa untuk beberapa variabel tiga, yaitu, hal-hal sepele yang tidak memuaskan.)2|C|
Di sisi lain, kita dapat membatasi jumlah instance yang memuaskan dengan jumlah yang dipenuhi oleh semua-nol tugas: ini akan menjadi , karena untuk setiap triplet variabel ada adalah salah satu klausa yang tidak dapat kita gunakan.2(7/8)|C|
Seseorang kemudian dapat membatasi jumlah instance yang memuaskan dengan mengalikannya dengan . Karena , saya kira ini hanya mengubah istilah pesanan kecil ...2n |C|=O(n3)
sumber
Jawaban ini hanya berkaitan dengan tingkat pertumbuhan jumlah instance yang memuaskan.
Himpunan jarang jika jumlah string n-bit dalam himpunan dibatasi oleh (untuk beberapa konstanta ) selain itu padat. Diketahui bahwa satisfiability (NP-complete) dan Unsatisfiability (CoNP-complete) keduanya merupakan set yang padat. Ada set lengkap lengkap iff .O ( n k ) k N P P = N PA O(nk) k NP P=NP
sumber