Oracles in NP(NP) are sufficient for exact learning
Oracles in NP(NP) are sufficient for exact learning
Johannes Köbler and Wolfgang Lindner
Abstract:
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).
Ps-File: Oracles in NP(NP) are Sufficient for Exact Learning
zuletzt geändert:
31.10.05
SK
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English