1992 · 215 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryTheory Of ComputationCircuit ComplexityRandomized ComputationBoolean SatisfiabilityBoolean Satisfiability ProblemCircuit SatisfiabilityComplexity Of SatisfiabilityConjunctive Normal FormSatisfiabilitySatisfiability ProblemUnsatisfiability
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 c<(0.25)2/sup k//k; in fact, they present a linear-time algorithm that satisfies F with probability 1-o(1). In addition, they establish a threshold for 2-SAT: if k = 2 then F is satisfiable with probability 1-o(1) whenever c<1 and unsatisfiable with probability 1-o(1) whenever c>1.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
7
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
On the Complexity of Timetable and Multicommodity Flow Problems
Shimon Even, Alon Itai, Adi Shamir · SIAM Journal on Computing · 1976 · 1.1K citations
Many hard examples for resolution
Vašek Chvátal, Endre Szemerédi · Journal of the ACM · 1988 · 445 citations · Full text
A Threshold for Unsatisfiability
Andreas Goerdt · Journal of Computer and System Sciences · 1996 · 240 citations