|
NeuroCOLT
Technical Report NC-TR-97-036
A
Dichotomy Theorem for Learning Quantified Boolean Formulas
Victor
Dalmau
Universitat Politecnica de Catalunya
Spain
Abstract
We consider the following classes of quantified boolean formulas.
Fix a finite set of basic boolean functions. Take conjunctions of
these basic functions applied to variables and constants in arbitrary
way. Finally quantify existentially or universally some of the variables.
We prove the following dichotomy theorem: For any set of
basic boolean functions, the resulting set of formulas is either polynomially
learnable from equivalence queries alone or else it is not PAC-predictable
even with membership queries under cryptographic assumptions. Furthermore
we identify precisely which sets of basic functions are in which of
the two cases.
Download Compressed Postscript
|