Upper bounds on the satisfiability threshold
From MaRDI portal
Publication:5958807
DOI10.1016/S0304-3975(01)00161-XzbMath0983.68082MaRDI QIDQ5958807
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
History and Prospects for First-Order Automated Deduction, Regular random \(k\)-SAT: Properties of balanced formulas, The large deviations of the whitening process in random constraint satisfaction problems, On the freezing of variables in random constraint satisfaction problems, On the satisfiability threshold of formulas with three literals per clause, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Resolution complexity of random constraint satisfaction problems: Another half of the story, Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
Cites Work
- A threshold for unsatisfiability
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Length of prime implicants and number of solutions of random CNF formulae
- Experimental results on the crossover point in random 3-SAT
- The scaling window of the 2-SAT transition
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- Many hard examples for resolution
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Bounding the unsatisfiability threshold of random 3-SAT
- Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
- Tail bounds for occupancy and the satisfiability threshold conjecture
- On Random 3-sat
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- A threshold for unsatisfiability
- Determining computational complexity from characteristic ‘phase transitions’
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Lower bounds for random 3-SAT via differential equations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
