PAC Meditation on Boolean Formulas.
Bruno ApolloniFabio BaraghiniGiorgio PalmasPublished in: SARA (2002)
Keyphrases
- boolean formula
- membership queries
- concept class
- pac learning
- sat solvers
- np complete
- practical problems
- boolean variables
- conjunctive normal form
- sample complexity
- linear constraints
- unsatisfiable cores
- equivalence queries
- boolean functions
- learning algorithm
- sample size
- vc dimension
- upper bound
- sat problem
- efficient learning
- binary decision diagrams
- concept classes
- statistical queries
- max sat
- special case
- learning problems
- constraint satisfaction
- search strategies
- learning theory