Mick gets some (the odds are on his side) (satisfiability)
- 1 January 1992
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 620-627
- https://doi.org/10.1109/sfcs.1992.267789
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 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 c1.Keywords
This publication has 6 references indexed in Scilit:
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problemInformation Sciences, 1990
- Many hard examples for resolutionJournal of the ACM, 1988
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problemDiscrete Applied Mathematics, 1983
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971