A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas
Hiroki MorizumiPublished in: CoRR (2008)
Keyphrases
- boolean functions
- boolean formula
- membership queries
- read once formulas
- binary decision diagrams
- polynomial size
- conjunctive normal form
- uniform distribution
- randomly generated
- np complete
- practical problems
- boolean variables
- bounded treewidth
- sat solvers
- dnf formulas
- disjunctive normal form
- pac learning
- machine learning
- worst case
- learning algorithm
- multi valued
- objective function
- linear constraints
- computational complexity