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
