Polynomial time truth-table reductions to p-selective sets

Agrawal, M. ; Arvind, V. (1994) Polynomial time truth-table reductions to p-selective sets Proceedings of the Ninth Annual Structure in Complexity Theory Conference, 1994 . pp. 24-30.

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...

Related URL: http://dx.doi.org/10.1109/SCT.1994.315821

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 ModkP classes (k>2) we show that if ModkP is o(log n)-truth-table reducible to a p-selective set then ModkP=P.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:95354
Deposited On:07 Nov 2012 04:44
Last Modified:07 Nov 2012 04:44

Repository Staff Only: item control page