Polynomial time truth-table reductions to p-selective sets

摘要

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 /spl Kscrspl isin/{NP, PP, C=P, /spl oplus/P) we show that if /spl Kscr/ is quasi-linear truth-table reducible to a p-selective set then /spl Kscr/=P. For other Mod/sub k/P classes (k<2) we show that if Mod/sub k/P is o(log n)-truth-table reducible to a p-selective set then Mod/sub k/P=P.