Upper bounds on the satisfiability threshold
From MaRDI portal
We present a survey of upper bounds which has been established up to now on the satisfiability threshold of random \(k\)-SAT formulae. The ideas which led to these bounds and the techniques used to obtain them, are explained. A companion paper in this volume present a survey of the lower bounds.
Recommendations
Cites work
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- A threshold for unsatisfiability
- A threshold for unsatisfiability
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Approximating the unsatisfiability threshold of random formulas
- Approximating the unsatisfiability threshold of random formulas (extended abstract)
- Bounding the unsatisfiability threshold of random 3-SAT
- Determining computational complexity from characteristic ``phase transitions
- Experimental results on the crossover point in random 3-SAT
- scientific article; zbMATH DE number 437557 (Why is no real title available?)
- scientific article; zbMATH DE number 3954272 (Why is no real title available?)
- scientific article; zbMATH DE number 1256700 (Why is no real title available?)
- scientific article; zbMATH DE number 1114008 (Why is no real title available?)
- scientific article; zbMATH DE number 1445295 (Why is no real title available?)
- scientific article; zbMATH DE number 956858 (Why is no real title available?)
- Length of prime implicants and number of solutions of random CNF formulae
- Lower bounds for random 3-SAT via differential equations
- Many hard examples for resolution
- On Random 3-sat
- 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
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- Sharp thresholds of graph properties, and the k-sat problem
- Tail bounds for occupancy and the satisfiability threshold conjecture
- The scaling window of the 2-SAT transition
Cited in
(16)- On the satisfiability threshold of formulas with three literals per clause
- On the freezing of variables in random constraint satisfaction problems
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- Resolution complexity of random constraint satisfaction problems: Another half of the story
- Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
- A threshold for a polynomial solution of \#2SAT
- New upper bounds for the problem of maximal satisfiability
- The large deviations of the whitening process in random constraint satisfaction problems
- Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
- SAT-Based Horn Least Upper Bounds
- History and prospects for first-order automated deduction
- New Upper Bounds for Maximum Satisfiability
- A threshold for unsatisfiability
- Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Regular random \(k\)-SAT: Properties of balanced formulas
This page was built for publication: Upper bounds on the satisfiability threshold
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958807)
