Truth-table closure and Turing closure of average polynomial time have different measures in EXP
Rainer Schuler · 2002
Let P/sub P-comp/ denote the sets that are solvable in polynomial time on average under every polynomial time computable distribution on the instances. In this paper we show that the truth-table closure of P/sub P-comp/ has measure 0 in EXP. Since, as we show, EXP is Turing reducible to P/sub P-comp/, the Turing closure has measure 1 in EXP and thus, P/sub P-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 P/sub P-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.