Resource bounded measure and learnability
Wolfgang F. Lindner, Rainer Schuler, Osamu Watanabe · 2002
We consider the resource bounded measure of polynomial-time learnable subclasses of polynomial-size circuits. We show that if EXP/spl ne/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.