The Conjunctive Complexity of Quadratic Boolean Functions.
Katja LenzIngo WegenerPublished in: Theor. Comput. Sci. (1991)
Keyphrases
- boolean functions
- pseudo boolean functions
- disjunctive normal form
- uniform distribution
- computational complexity
- polynomial size
- functional properties
- threshold functions
- linear functions
- relevant variables
- linear threshold
- dnf formulae
- membership queries
- binary decision diagrams
- bounded treewidth
- pairwise
- read once formulas
- objective function
- modal logic
- heuristic search
- worst case