Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable. (Here $\epsilon$ is any small constant and $n$ is the number of variables.) If the number is $(\alpha - \epsilon) n$ or less, they are almost surely satisfiable.

The thesis Belief propagation algorithms for constraint satisfaction problems by Elitza Nikolaeva Maneva challenges the problem from the angle of belief propagation known in information theory. On page 13, it says $3.52<\alpha<4.51$ if $\alpha$ exists.

What are the best known bounds for $\alpha$?

share|improve this question
1  
See also question cstheory.stackexchange.com/q/1130 –  András Salamon Jan 12 '13 at 10:07
add comment

2 Answers 2

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.

The unsatisfiability threshold is known to be at most 4.4898, a slight improvement since Maneva's 2001 thesis.

The satisfiability threshold is known to be at least 3.52, which is unchanged from the time of Maneva's thesis.

  • A. C. Kaporis, L. M. Kirousis, E. G. Lalas. The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Random Structures and Algorithms 28, 2006, 444–480. doi:10.1002/rsa.20104

These bounds were recently cited by Achlioptas and Menchaca-Mendez as the best known to date.

  • D. Achlioptas, R. Menchaca-Mendez. Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method, ICALP 2012, LNCS 7391, 1–12. doi:10.1007/978-3-642-31594-7_1
share|improve this answer
add comment

this is a new 58 page paper (32 refs) accepted to STOC 2013 that surveys and advances the area of determining the precise k-SAT threshhold, building especially from results borrowed from statistical physics. from the abstract

Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the k-SAT threshold up to an additive $\ln 2 − {1 \over 2} +O(1/k) \approx 0.19$

Going after the k-SAT threshhold by Coja-Oghlan and Konstantinos Panagiotou

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.