Random boolean formulas representing any boolean function with asymptotically equal probability.
Petr SavickýPublished in: Discret. Math. (1990)
Keyphrases
- boolean functions
- boolean formula
- randomly generated
- membership queries
- binary decision diagrams
- uniform distribution
- read once formulas
- conjunctive normal form
- boolean variables
- multi valued
- dnf formulas
- sat instances
- classification noise
- sample size
- equivalence queries
- pac learning
- simulated annealing
- random instances
- polynomial size
- efficient learning
- linear constraints