Quasi-linear truth-table reductions to p-selective sets

Agrawal, M. ; Arvind, V. (1996) Quasi-linear truth-table reductions to p-selective sets Theoretical Computer Science, 158 (1-2). pp. 361-370. ISSN 0304-3975

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/030439...

Related URL: http://dx.doi.org/10.1016/0304-3975(95)00167-0

Abstract

We show that if SAT is quasi-linear truth-table reducible to a p-selective set then NP = P. As a consequence it follows that for a class , K ε {PP.C = P}, if every set in K is quasi-linear truth-table reducible to a p-selective set then K = P.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:20244
Deposited On:20 Nov 2010 14:48
Last Modified:10 May 2011 07:34

Repository Staff Only: item control page