SAT 2003
An Algorithm for SAT Above the Threshold
Abstract
Abstract We study algorithms for finding satisfying assignments of randomly generated 3-SAT formula. In particular, we consider distributions of highly constrained formulas (that is, “above the threshold” formulas) restricted to satisfiable instances. We obtain positive algorithmic results, showing that such formulas can be solved in low exponential time.
Authors
Keywords
No keywords are indexed for this paper.
Context
- Venue
- International Conference on Theory and Applications of Satisfiability Testing
- Archive span
- 2003-2025
- Indexed papers
- 824
- Paper id
- 869906713820551959