|
NeuroCOLT
Technical Report NC-TR-95-013
Learnability of
Kolmogorov-Easy Circuit Expressions Via Queries
Josè
L. Balcazar
Universitat Politecnica de Catalunya
Harry
Buhrman
CWI, Amsterdam
Montserrat
Hermo
Universidad del Païs Vasco
Abstract
Circuit expressions were introduced to provide a natural link between
Computational Learning and certain aspects of Structural Complexity.
Upper and lower bounds on the learnability of circuit expressions
are known. We study here the case in which the circuit expressions
are of low (time-bounded) Kolmogorov complexity. We show that these
are polynomial-time learnable from membership queries in the presence
of an NP oracle. We also exactly characterize the sets that have such
circuit expressions, and precisely identify the subclass whose circuit
expressions can be learned from membership queries alone. The extension
of the results to various Kolmogorov complexity bounds is discussed.
Download Compressed
Postscript
|