Typical random 3-SAT formulae and the satisfiability threshold
arXiv:cs/0211036
Abstract
We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.
References in corpus (6)
- The Scaling Window of the 2-SAT Transition
- Phase Transition in the Number Partitioning Problem
- Typical random 3-SAT formulae and the satisfiability threshold
- Exact solutions for diluted spin glasses and optimization problems
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- On the non-3-colourability of random graphs
Cited by in corpus (21)
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- The Scaling Window of the 2-SAT Transition
- Survey propagation: an algorithm for satisfiability
- Typical random 3-SAT formulae and the satisfiability threshold
- A better algorithm for random k-SAT
- Relaxation and Metastability in the RandomWalkSAT search procedure
- The backtracking survey propagation algorithm for solving random K-SAT problems
- Random MAX SAT, Random MAX CUT, and Their Phase Transitions
- Minimizing energy below the glass thresholds
- Criticality and Universality in the Unit-Propagation Search Rule
- The Asymptotic Order of the k-SAT Threshold
- Approximating the satisfiability threshold for random k-XOR-formulas
- Phase Transition for Random Quantified XOR-Formulas
- On the Max-Cut of Sparse Random Graphs
- Optimization and Physics: On the satisfiability of random Boolean formulae
- Statistical mechanics of optimization problems
- Phase Transition in Matched Formulas and a Heuristic for Biclique Satisfiability
- Complete convergence of message passing algorithms for some satisfiability problems
- Errata and Addenda to Mathematical Constants
- Second moment method for a family of boolean CSP
- Estimating Satisfiability