On the power of equivalence queries
Ricard Gavaldà · 1994
In 1990, Angluin showed that no class exhibiting a combinatorial property called "approximate fingerprints" can be identified exactly using polynomially many Equivalence queries (of polynomial size). Here we show that this is a necessary condition: every class without approximate fingerprints has an identification strategy that makes a polynomial number of Equivalence queries. Furthermore, if the class is "honest" in a technical sense, the computational power required by the strategy is within the polynomial-time hierarchy, so proving nonlearnability is at least as hard as showing P 6= NP. 1 Introduction Learning via queries is a well-studied model in computational learning. The types of queries that have been used most often in the design of learning algorithms are, by far, Membership and Equivalence queries. In this paper we focus on the second type. This research was partially supported by the ESPRIT Basic Research Actions Program of the EC under contract No. 7141 (proj...