Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams.
Luke FriedmanYixin XuPublished in: Electron. Colloquium Comput. Complex. (2013)
Keyphrases
- lower bound
- ordered binary decision diagrams
- upper bound
- average case complexity
- deterministic finite automaton
- branch and bound algorithm
- objective function
- np hard
- model checking
- branch and bound
- randomly generated
- vc dimension
- constraint satisfaction problems
- worst case
- constraint propagation
- quantified boolean formulae
- computational complexity
- search algorithm
- multi agent