On the Gap between the Complexity of SAT and Minimization for Certain Classes of Boolean Formulas.
Ondrej CepekStefan GurskýPublished in: ISAIM (2014)
Keyphrases
- boolean formula
- sat solvers
- boolean satisfiability
- np complete
- practical problems
- boolean variables
- sat problem
- linear constraints
- conjunctive normal form
- membership queries
- binary decision diagrams
- sat instances
- max sat
- boolean functions
- satisfiability problem
- constraint satisfaction
- search tree
- orders of magnitude
- cnf formula
- unsatisfiable cores
- learning algorithm
- propositional satisfiability
- decision problems
- np hard
- search algorithm
- data structure
- objective function