Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
verfasst von : Ryan C. Harkins, John M. Hitchcock
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper extends and improves work of Fortnow and Klivans [5], who showed that if a circuit class
$\mathcal{C}$
has an efficient learning algorithm in Angluin’s model of exact learning via equivalence and membership queries [2], then we have the lower bound EXP NP
$\not\subseteq \mathcal{C}$
. We use entirely different techniques involving betting games [4] to remove the NP oracle and improve the lower bound to EXP
$\not\subseteq \mathcal{C}$
. This shows that it is even more difficult to design a learning algorithm for
$\mathcal{C}$
than the results of Fortnow and Klivans indicated.