Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries.
Albert AtseriasPublished in: Computational Complexity Conference (2006)
Keyphrases
- black box
- polynomial size
- model counting
- dnf formulas
- exponential size
- black boxes
- boolean functions
- conjunctive normal form
- phase transition
- knowledge compilation
- white box
- random instances
- query processing
- satisfiability problem
- test cases
- query language
- query evaluation
- database
- bounded treewidth
- search algorithm
- membership queries
- source code
- decision trees