ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING

We show that the class of all circuits is exactly learnable in randomi zed expected polynomial time using weak subset and weak superset queri es. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly learnable in randomi zed expected polynomial time with equivalence queries and the aid of a n NP-oracle. We also show that circuits are exactly learnable in deter ministic polynomial time with equivalence queries and a Sigma(3)(p)-or acle. The hypothesis class for the above learning algorithms is the cl ass of circuits of larger-but polynomially related-size. Also, the alg orithms can be adapted to learn the class of DNF formulas with hypothe sis class consisting of depth-3 boolean AND-boolean OR-boolean AND for mulas (by the work of Angluin this is optimal in the sense that the hy pothesis class cannot be reduced to DNF formulas, i.e., depth-2 boolea n OR-boolean AND formulas). We also investigate the power of an NP-ora cle in the context of learning with membership queries. We show that t here are deterministic learning algorithms that use membership queries and an NP-oracle to learn: monotone boolean functions in time polynom ial in the DNF size and CNF size of the target formula; and the class of O(log n)-DNF boolean AND O(log n)-CNF formulas in time polynomial i n n. We also show that, with an NP-oracle and membership queries, ther e is a randomized expected polynomial time algorithm that learns any c lass that is learnable from membership queries with unlimited computat ional power. Using similar techniques, we show the following both for membership and for equivalence queries (when the hypotheses allowed ar e precisely the concepts in the class); any class learnable with unbou nded computational-power is learnable in deterministic polynomial time with a Sigma(5)(p)-oracle. Furthermore, we identify the combinatorial properties that completely determine learnability in this information -theoretic sense. Finally we point out a consequence of our result in structural complexity theory showing that if every NP set has polynomi al-size circuits then the polynomial hierarchy collapses to ZPP(NP). ( C) 1996 Academic Press, Inc.