Ada berapa tautologi?

Mengingat , berapa banyak k -DNF dengan n variabel dan klausa m adalah tautologi? (atau berapa banyak k -CNF yang tidak memuaskan?)$m, n, k$$k$$n$$m$$k$

Jawabannya tergantung pada , m , dan n . Hitungan yang tepat umumnya tidak diketahui, tetapi ada fenomena "ambang" yang untuk sebagian besar pengaturan k , m , n , hampir semua contoh k -SAT memuaskan, atau hampir semua contoh tidak memuaskan. Misalnya, ketika k = 3 , telah diamati secara empiris bahwa ketika m < 4,27 n , semua kecuali o ( 1 ) fraksi dari instance 3-SAT yang memuaskan, dan ketika m > 4,27 n , semua kecuali a $k$$m$$n$$k$$m$$n$$k$$k=3$$m < 4.27 n$$o(1)$$m > 4.27n$$o(1)$ fraksi tidak memuaskan. (Ada juga bukti batas yang dikenal.)

Satu titik awal adalah "Urutan Asimptotik dari Ambang k-SAT" .

Amin Coja-Oghlan juga telah melakukan banyak pekerjaan pada masalah ambang batas kepuasan ini.

Ini adalah komentar yang diperluas untuk melengkapi jawaban Ryan, yang berkaitan dengan ambang batas di mana jumlah klausa menjadi cukup besar sehingga instance hampir pasti tidak memuaskan. Kita juga dapat menghitung ambang yang jauh lebih besar di mana jumlah klausa memaksa ketidakpuasan ketika melebihi fungsi .$n$

Perhatikan bahwa beberapa masalah teknis perlu ditangani. Jika klausa berulang dihitung dalam , maka m dapat dibuat sebesar yang diinginkan tanpa mengubah n . Ini akan menghancurkan sebagian besar hubungan antara m dan n . Jadi asumsikan bahwa m adalah jumlah klausa yang berbeda. Kita perlu memutuskan detail lain, apakah instance dikodekan sehingga urutan literal dalam klausa atau urutan klausa dalam instance instance. Misalkan ini tidak penting, jadi dua instance dianggap setara jika mengandung klausa yang sama, dan dua klausa setara jika mengandung literal yang sama. Dengan asumsi-asumsi ini, kita sekarang dapat mengikat sejumlah klausa berbeda yang dapat diekspresikan dengan$m$$m$$n$$m$$n$$m$ variabel. Setiap klausa dapat memiliki setiap variabel yang terjadi secara positif atau negatif, atau tidak sama sekali, dan kemudian m ≤ 3 n .$n$$m\le 3^n$

Pertama, pertimbangkan SAT tanpa batasan pada . Apa yang terbesar m sehingga turunannya memuaskan? Tanpa kehilangan sifat umum kita dapat menganggap bahwa penugasan semua-nol adalah solusi. Kemudian ada 3 n - 2 n klausa berbeda yang konsisten dengan solusi ini, masing-masing berisi setidaknya satu literasi yang dinegasikan. Karenanya m ≤ 3 n - 2 n untuk setiap instance yang memuaskan. Contoh yang terdiri dari semua klausa yang masing-masing berisi setidaknya satu literasi yang dinegasikan memiliki banyak klausa ini, dan dipenuhi oleh penugasan yang semuanya nol. Lebih lanjut, dengan prinsip lubang kubah setiap contoh dengan setidaknya 3 $k$$m$$3^n-2^n$$m\le 3^n-2^n$ klausa adalah unsatisfiable.$3^n-2^n+1$

Ini menghasilkan himpunan bagian yang berbeda dari klausa tersebut, masing-masing mewakili contoh berbeda yang dipenuhi oleh beberapa penugasan. Sebagai perbandingan, jumlah total instance yang berbeda adalah 2 3 n .$2^{3^n-2^n}$$2^{3^n}$

Sekarang memodifikasi atas untuk contoh di mana masing-masing klausa memiliki paling literal, ada Σ k i = 0 ($k$klausul tersebut berbeda, danΣ k i = 0 ($\sum_{i=0}^k \binom{n}{i}2^i$ klausa di mana tidak ada literal negatif, jadim≤∑ k i = 0 ($\sum_{i=0}^k \binom{n}{i}$untuk contoh yang memuaskan, danm yanglebih besartidak memuaskan. Maka ada2∑ k i = 0 ($m\le \sum_{i=0}^k \binom{n}{i}(2^i - 1)$$m$contoh dipenuhi oleh setiap tugas tertentu, dari total2Σ k i = 0 ($2^{\sum_{i=0}^k \binom{n}{i}(2^i - 1)}$k-SAT instance.$2^{\sum_{i=0}^k \binom{n}{i}2^i}$ $k$