The random-k-sat tag has no wiki summary.
23
votes
2answers
239 views
Current tightest bounds for critical 3-SAT density
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 ...
16
votes
1answer
289 views
What is the counting complexity of random 2-SAT?
Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated ...
4
votes
1answer
227 views
Approximating Random MAX-k-SAT
It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity.
Should ...
15
votes
1answer
363 views
Average-case tautologies/contradictions, beyond the random k-CNF model
It is well known that random $ k $-CNF formulas over $ n $ variables with $ cn $ clauses are unsatisfiable (i.e. they are contradictions) with high probability, for sufficiently large constant $ c $. ...
