Apa definisi tepat dari Random K-SAT?

Ada 4 batasan berbeda yang bisa kita miliki ketika mendefinisikan K-SAT Acak.
1) Jumlah total literal dalam klausa tertentu persis K atau AT paling banyak K
2) Literal yang diberikan dapat digunakan dengan atau tanpa penggantian dalam klausa yang sama (A atau A atau A)
3) Variabel yang diberikan dapat digunakan dengan atau tanpa penggantian dalam klausa yang sama (A atau ~ A atau ~ A)
4) Klausa yang diberikan dapat digunakan dengan atau tanpa penggantian dalam formula tertentu
Apa definisi paling "benar"? Apa kontra dan kelebihan dari menggunakan definisi yang berbeda ini?

$k$

$k$ $k$

Dua model utama:

The Selman Model random - Berulang klausul yang diperbolehkan . Kyle memberikan referensi yang bagus dalam komentar untuk jawabannya, tetapi salah berasumsi bahwa model tersebut tidak mengizinkan klausa berulang. Versi yang tertaut (sedikit berbeda) dari makalah ini berisi diskusi yang lebih rinci dari model acak di Bagian 3: "Metode generasi ini memungkinkan klausa duplikat dalam sebuah rumus ... Namun, karena N mendapat duplikat besar akan menjadi langka karena kita umumnya pilih hanya sejumlah klausa linier. "

$m$$2^k {n \choose k}$

Kesetaraan lokasi transisi fase :

Namun, transisi fase (ambang kepuasan 50%) terjadi pada rasio klausa-untuk-variabel yang sama terlepas dari mana model ini dipilih karena alasan yang mendasar bahwa Selman et al. dicatat di kertas mereka.

Misalkan menunjukkan jumlah pasangan klausa yang identik yang diharapkan dalam contoh Selman acak -SAT. Probabilitas pasangan klausa tertentu yang identik adalah , sedangkan jumlah total pasangan klausa adalah . Dengan linearitas harapan, .$A(n,m,k)$$(n,m,k)$$p = 1/(2^k {n \choose k})$$N = {m \choose 2}$$A(n,m,k) = p \cdot N = {m \choose 2}/{2^k {n \choose k}}$

Dengan Teorema 3 dalam [1], batas atas yang dapat dibuktikan pada lokasi transisi fase -SAT, menggunakan model Achlioptas terjadi ketika . Memperbaiki dan pengaturan kita dapatkan$k$$m = O(2^k n)$$k \geq 3$$m = O(2^k n)$

$A(n,m,k) = {m \choose 2}/{2^k {n \choose k}} = O(m^2)/O(n^k) = O(n^2)/O(n^k)$ .

Kemudian, karena , , yang berarti bahwa dalam harapan akan ada nol klausa berulang di sekitar -SAT transisi fase ketika menghasilkan rumus SAT acak menggunakan model Selman.$k \geq 3$$\displaystyle \lim_{n \rightarrow \infty} O(n^2)/O(n^k) = 0$$k$

Promosi diri yang tidak tahu malu - Saya membahas topik ini secara singkat di Bagian 4.1 dari tesis master saya .

QBF acak

Ternyata, situasinya jauh lebih menarik untuk QBF acak. Apa AFAIK tiga makalah pertama tentang QBF acak masing-masing mengusulkan model acak baru, mengkritik pendahulunya.

Lihat makalah berikut:

• Cadoli et al. "Analisis Eksperimental Biaya Komputasi untuk Mengevaluasi Formula Boolean yang Dihitung." AI * IA 1997
• Gent + Walsh "Melampaui NP: transisi fase QSAT." AAAI / IAAI 1999
• Chen + Interian "Sebuah Model untuk Menghasilkan Rumus Boolean Kuantitatif yang Dihitung." IJCAI 2005

[Diedit untuk kejelasan]

Definisi yang paling banyak digunakan dalam literatur penelitian adalah definisi yang membutuhkan tepat variabel k berbeda per klausa, dan tidak ada klausa duplikat. Jika Anda mengendurkan batasan variabel yang berbeda, sebagian besar penelitian yang ada tidak akan masuk akal bagi Anda karena hasil Anda tidak akan cocok dengan hasil mereka. Transisi fase sat / unsat yang terkenal akan terjadi pada rasio klausul-variabel yang berbeda (jika transisi ada sama sekali) dan Anda tidak akan menemukan contoh-contoh SAT yang sulit di mana Anda harapkan dari literatur.