Randomness, learnability, and betting games

Abstract

Randomness has long been described in many fashions. From a predictability standpoint, a sequence is random if no scheme (under various definitions of computability) can predict the next bit any better than a coin-flip. From an observational standpoint, a sequence is random if it is not compressible, or in other words, it has high Kolmogorov Complexity. Under the prediction paradigm, we combine learning algorithms from Computation Learning Theory with Resource Bounded Measure and Dimension to show various interesting classes are learnable thus have p-dimension 0. We extend some of these techniques to the set of Kolmogorov random strings.

It has long been known that if NP has a sparse complete set under various types of polynomial-time reductions, and in particular, if NP ⊆ P _btt(P_ctt(SPARSE)), then P = NP. Under the assumption that NP does not have measure 0, a proof that (P_btt(P_ctt(SPARSE))) does have measure 0 would imply that NP does not have sparse complete sets under the composed reduction. We show the stronger result that dim_p(P _{α log n–tt}(P _ctt(DENSE^c))) = 0 by combining Maass and Turán's algorithm for learning halfspaces with Hitchcock's result that [special characters omitted](2^cn, 2^cn, 2^{o(n )}), the set of all sequences 2^cn-time reducible to concepts learnable in 2^cn time with a subexponential mistake bound, has p-dimension 0.

In a similar fashion, we show how the notion of reliable reductions of Arvind, et al., yields a “one-sided” learning algorithm, i.e. an he First Learneralgorithm that learns a subset of the target concept. Using this, we can show that P_hd(P_ctt(DENSE ^c)) has p-dimension 0. We can then extend this to show that P_hd(P_ctt(R_C)) has p-dimension 0, where R_C is the set of random strings as defined by Kolmogorov Complexity. Thus we can conclude that if μ_p(NP) ≠ 0, then NP does not have any non-dense complete sets under the composed bounded-truth-table-conjunctive reduction, or the composed Hausdorff-conjunctive redunction. Furthermore, we can conclude that NP cannot be characterized by reductions to random strings using only the composed Hausdorff-conjunctive reduction.

The best unconditional circuit lower bound known is that the class MA _EXP requires exponential-size circuits, but one of the lowest conditional circuit lower bounds was given by Fortnow and Klivans, who showed that if a class [special characters omitted] of circuits is learnable in the Exact Learning model of Angluin, then EXP^NP is not contained in [special characters omitted]. We combine Exact Learning (with membership queries) with the betting games of Buhrman, et al., to improve this bound to show, under a weaker hypothesis, that EXP cannot be contained in [special characters omitted]. However, it seems unlikely that we can improve our results to use Valiant's PAC learning model, which would have been advantageous given the result of Bshouty, et al., that circuits are learnable in ZPP^NP. The reason for this is that randomized betting games yield practically no greater advantage than the randomized martingales of Moser, and Regan and Sivakumar.