Truth-table closure and Turing closure of average polynomial time have different measures in EXP

Let PP-comp denote the sets that are solvable in polynomial time on average under every polynomialtime computable distribution on the instances. In this paper we show that the truth-table closure of PP-comp has measure 0 in EXP. Since, as we show, EXP is Turing reducible to PP-comp , the Turing closure has measure 1 in EXP and thus, PP-comp is an example of a subclass of E such that the closure under truth-table reduction and the closure under Turing reduction have different measures in EXP. Furthermore, it is shown that there exists a set A in PP-comp such that for every k, the class of sets L such that A is k-truth-table reducible to L has measure 0 in EXP. 1 Introduction A randomized problem (or distributional problem) is a pair consisting of a decision problem and a density function. A randomized decision problem (A; ¯) is solvable in average polynomial time ((A; ¯) is in AP) if there exists a deterministic Turing machine M such that A = L(M ) and TimeM , the running time of M ..