Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Oracles in NP(NP) are sufficient for exact learning

Johannes Köbler and Wolfgang Lindner


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).

Ps-File: Oracles in NP(NP) are Sufficient for Exact Learning