Johannes Köbler and Wolfgang Lindner
Abstract:
We consider representation classes of polynomial query complexity in
Angluin's exact learning model with all three possible combinations of
membership and (proper) equivalence queries allowed. We show that in
all three cases, polynomial query complexity implies already
polynomial-time learnability where the learner additionally has access
to an oracle in NP(NP). As an application, it follows that boolean
circuits are polynomial-time learnable with equivalence queries and
the help of an oracle in NP(NP). Our results are based on known
combinatorial properties characterizing polynomial query complexity
and a careful application of hashing-techniques.