Resource Bounded Measure and Learnability.
Wolfgang Lindner, Rainer Schuler and Osamu Watanabe, Proc. 12th Annual IEEE Conference on Computational Complexity, 1998.
Abstract:
We consider the resource bounded measure of polynomial-time
learnable subclasses of polynomial-size circuits. We show that if
EXP not equal to MA, then every PAC-learnable subclass of P/poly has
EXP-measure zero. We introduce a nonuniformly computable variant
of resource bounded measure and show that, for every fixed
polynomial q, any polynomial-time learnable subclass of circuits
of size q has measure zero with respect to P/poly. We relate our
results to the question whether Boolean Circuits are polynomial-time
learnable.
email: schuler@informatik.uni-ulm.de
[paper]
[paper.ps.gz]