Boolean functions with a simple certificate for CNF complexity.
Ondrej CepekPetr KuceraPetr SavickýPublished in: Discret. Appl. Math. (2012)
Keyphrases
- boolean functions
- uniform distribution
- dnf formulae
- polynomial size
- randomly generated
- threshold functions
- prime implicants
- relevant variables
- membership queries
- disjunctive normal form
- functional properties
- linear threshold
- read once formulas
- computational complexity
- bounded treewidth
- binary decision diagrams
- belief revision
- worst case
- linear functions
- upper bound