Random Boolean Formulas Representing any Boolean Function with Asymptotically Equal Probability (Extended Abstract).
Petr SavickýPublished in: MFCS (1988)
Keyphrases
- extended abstract
- boolean functions
- boolean formula
- randomly generated
- membership queries
- binary decision diagrams
- uniform distribution
- read once formulas
- boolean variables
- conjunctive normal form
- disjunctive normal form
- pac learning
- multi valued
- equivalence queries
- sat solvers
- target concept
- efficient learning
- statistical queries
- dnf formulas
- sat instances
- machine learning