Abstract
Johannes Köbler and Wolfgang Lindner
Abstract:
We study the learnability of representation classes in Angluin's exact
learning model. In particular, we consider the following three query
types: equivalence queries, equivalence and membership queries, and
membership queries only. We show in all three cases that polynomial
query complexity implies already polynomial-time learnability,
provided that the learner additionally has access to an oracle in
NP(NP)$. It follows that boolean circuits are polynomial-time
learnable with equivalence queries and the help of an oracle in
NP(NP).