HOW MANY QUERIES ARE NEEDED TO LEARN

We investigate the query complexity of exact learning in the membershi p and (proper) equivalence query model. We give a complete characteriz ation of concept classes that are learnable with a polynomial number o f polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query co mplexity has previously been used to prove lower bounds on the time co mplexity of exact learning. We show a new relationship between query c omplexity and time complexity in exact learning: if any ''honest'' cla ss is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P not equal NP. In particu lar, we show that an honest class is exactly polynomial-query learnabl e if and only if it is learnable using an oracle for Sigma(4)(p).