Mick gets some (the odds are on his side) (satisfiability)

1992/01/01 by Vašek Chvátal, Bruce Reed · 4 citations
Computer Science · Mathematics · Chemistry · #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Advanced Graph Theory Research #Combinatorics #Satisfiability #Complement (music) #Conjunctive normal form #Mathematics #Probability distribution #Discrete mathematics #Infinity #Value (mathematics) #Boolean satisfiability problem #Statistics #Chemistry

paper · doi:10.1109/sfcs.1992.267789

openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Consider a randomly generated boolean formula F (in the conjunctive normal form) with m clauses of size k over n variables; k is fixed at any value greater than 1, but n tends to infinity and m = (1 + o(1))cn for some c depending only on k. It is easy to see that F is unsatisfiable with probability 1-o(1) whenever c>(ln 2)2/sup k/; the authors complement this observation by proving that F is satisfiable with probability 1-o(1) whenever c1.>

Citations

• On the Complexity of Timetable and Multicommodity Flow Problems
• A Threshold for Unsatisfiability
• A linear-time algorithm for testing the truth of certain quantified boolean formulas
• The complexity of theorem-proving procedures

Cited by

• Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test
• On the critical exponents of random k‐SAT
• Stochastic Boolean Satisfiability
• 2-satisfiability [wikipedia]