Complexity theoretic hardness results for query learning
From MaRDI portal
Publication:1266164
DOI10.1007/PL00001593zbMath0903.68157OpenAlexW2072682576MaRDI QIDQ1266164
Lisa Hellerstein, Leonard Pitt, Tibor Hegedűs, Howard Aizenstein
Publication date: 26 October 1998
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00001593
Learning and adaptive systems in artificial intelligence (68T05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Exact learning from an honest teacher that answers membership queries, Learning read-constant polynomials of constant degree modulo composites, Exact learning of DNF formulas using DNF hypotheses, Decision lists and related Boolean functions, On the Nonlearnability of a Single Spiking Neuron, Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds, Version spaces and the consistency problem, Theory revision with queries: Horn, read-once, and parity formulas, The complexity of learning concept classes with polynomial general dimension
