Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances.
Hans van MaarenLinda van NordenPublished in: Ann. Math. Artif. Intell. (2005)
Keyphrases
- random sat instances
- boolean formula
- sat problem
- sat solving
- sat instances
- sat solvers
- stochastic local search
- conjunctive normal form
- clause learning
- boolean satisfiability
- max sat
- randomly generated
- propositional satisfiability
- satisfiability problem
- random instances
- quantified boolean formulas
- np complete
- cnf formula
- random sat
- unit propagation
- propositional logic
- boolean functions
- practical problems
- phase transition
- truth assignment
- constraint satisfaction problems
- tree search
- np hard
- davis putnam
- horn clauses
- linear constraints
- computational properties
- search algorithm
- horn theories
- lower bound
- search strategies
- propositional formulas
- graph coloring
- knowledge compilation
- branch and bound
- orders of magnitude