Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques
Amin Coja-OghlanAndreas GoerdtAndré LankaFrank SchädlichPublished in: Electron. Colloquium Comput. Complex. (2003)
Keyphrases
- propositional formulas
- cnf formula
- max sat
- random sat
- propositional logic
- normal form
- propositional satisfiability
- truth assignment
- sat problem
- stochastic local search
- np complete
- satisfiability problem
- sat solvers
- central limit theorem
- randomly generated
- approximation algorithms
- quantifier free
- closed form
- unsatisfiable cores
- branch and bound algorithm
- approximation error
- randomly chosen
- error bounds
- phase transition
- boolean formula
- clause learning
- boolean satisfiability
- mathematical formulas
- knowledge compilation
- random sat instances
- search space
- rewrite systems
- conjunctive normal form
- queueing networks