A Dichotomy Theorem for Learning Quantified Boolean Formulas |
| |
Authors: | Dalmau Víictor |
| |
Affiliation: | (1) Departament LSI, Universitat Politècnica de Catalunya, Campus Nord, Mòdul C5, Jordi Girona Salgado, 1-3, Barcelona, 08034, 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 ways. 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. |
| |
Keywords: | computational learning theory qualified boolean formulas dichotomy theorems |
本文献已被 SpringerLink 等数据库收录! |
|