A continuous-discontinuous second-order transition in the satisfiability of random Horn-SAT formulas.
Cristopher MooreGabriel IstrateDemetrios D. DemopoulosMoshe Y. VardiPublished in: Random Struct. Algorithms (2007)
Keyphrases
- random sat
- random sat instances
- sat problem
- satisfiability problem
- phase transition
- cnf formula
- truth assignment
- propositional formulas
- propositional logic
- boolean formula
- conjunctive normal form
- stochastic local search
- max sat
- np complete
- sat instances
- knowledge compilation
- davis putnam
- boolean satisfiability
- sat solving
- sat solvers
- np hard
- satisfiability testing
- randomly generated
- continuous functions
- propositional satisfiability
- random instances
- constraint satisfaction problems
- temporal logic
- search algorithm
- horn clauses
- constraint satisfaction
- branch and bound algorithm
- higher order
- randomly chosen
- sat encodings
- first order logic
- quantified boolean formulas
- horn formulas
- computational complexity