Polynomial time truth-table reductions to p-selective sets

Abstract

We make an elaborate analysis of the intervals defined by the ordered list of queries to the p-selective set. It turns out that the properties we derive are strong enough to get a collapse to P for several complexity classes, assuming that they are quasi-linear truth-table reducible (or in some cases o(logn)-tt reducible) to a p-selective set. More specifically, for any class & Kscr;∈{NP, PP, C=P, ⊕P) we show that if & Kscr; is quasi-linear truth-table reducible to a p-selective set then & Kscr;=P. For other Mod_kP classes (k>2) we show that if Mod_kP is o(log n)-truth-table reducible to a p-selective set then ModkP=P.