Acak 3-SAT: Apa rentang eksperimental konsensus ambang batas?

Rasio kritis klausa terhadap variabel untuk acak 3-SAT adalah lebih dari 3 dan kurang dari 6, dan tampaknya secara umum digambarkan sebagai "sekitar 4,2" atau "sekitar 4,25". Mezard, Parisi, dan Zecchina membuktikan (dalam pengertian fisika) bahwa rasio kritis adalah 4,256, sedangkan penulis pertama dan ketiga membuktikan bahwa itu adalah 4,267.

What is the range of values that the critical ratio could possibly take?

Motivasi saya untuk mengajukan pertanyaan ini adalah jika rasionya bisa , maka pengurangan standar 3-SAT untuk NAE-3-SAT (mengubahklausa danvariabel menjadiklausa danvariabel) memberikan rasio, yang tampaknya tidak mungkin tapi akan cukup keren. $2+\sqrt{5} \approx 4.236$ $m$ $n$ $2m$ $m+n+1$ $\phi$

sat phase-transition random-k-sat Andrew D. King
sumber

Anda perlu mendefinisikan apa artinya rasio menjadi kritis.

Tyson Williams

Saya pikir ini adalah terminologi standar: rasio kritis adalah bilangan real

sedemikian rupa sehingga rumus 3-SAT acak dengan

klausa hampir pasti memuaskan, dan rumus 3-SAT acak dengan

klausa hampir pasti tidak memuaskan. hampir pasti di sini berarti probabilitasnya menjadi

seperti

α

$\alpha$

< α n

$< \alpha n$

> α n

$> \alpha n$

1

$1$

n \to \infty

$n \to \infty$

Sasho Nikolov

kemungkinan rangkap dari Apa batas atas dan bawah yang paling dikenal saat ini pada ambang batas kepuasan (un) untuk k-sat acak dan / atau 3-sat?

András Salamon

Saya berpendapat bahwa pertanyaannya berbeda. Saya mencari beberapa perkiraan dari serangkaian nilai yang, katakanlah, tidak akan mengejutkan setiap ahli di komunitas. Saya tidak berpikir apa pun di bawah 4, misalnya, memenuhi syarat. (Saya menyadari bahwa ini, sampai batas tertentu, tergantung pada jarak tempuh individual.)

Andrew D. King

Acak 3-SAT: Apa rentang eksperimental konsensus ambang batas?

Jawaban: