On the multiplicative complexity of Boolean functions over the basis (cap, +, 1).
Joan BoyarRené PeraltaDenis PochuevPublished in: Theor. Comput. Sci. (2000)
Keyphrases
- boolean functions
- uniform distribution
- polynomial size
- threshold functions
- relevant variables
- dnf formulae
- prime implicants
- computational complexity
- functional properties
- membership queries
- multi valued
- binary decision diagrams
- dnf formulas
- read once formulas
- bi decomposition
- linear threshold
- disjunctive normal form
- abductive reasoning
- satisfiability problem