A dichotomy theorem for learning quantified Boolean formulas
Víctor Dalmau · 1997
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. Work supported in part by the Spanish Government through grant AP94 43716784 and the DGICYT (project BP92-0709) and the EC through the Esprit BRA Program (Working Group 8556, NeuroColt and project 20244, ALCOM IT). 1 Introduction The problem of learning an unknown boolean formula under some determined protocol has been widely studied. It is well know...