Agrawal, Manindra (2002) For completeness, sublogarithmic space is no space Information Processing Letters, 82 (6). pp. 321-325. ISSN 0020-0190
![[img]](http://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Publisher Version
132kB |
Official URL: http://linkinghub.elsevier.com/retrieve/pii/S00200...
Related URL: http://dx.doi.org/10.1016/S0020-0190(01)00296-4
Abstract
It is shown that for any class C closed under linear-time reductions, the complete sets for C under sublogarithmic reductions are also complete under 2DFA reductions, and thus are isomorphic under first-order reductions.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Isomorphisms; Completeness; Sublogarithmic Reductions; Computational Complexity |
| ID Code: | 20224 |
| Deposited On: | 20 Nov 2010 14:49 |
| Last Modified: | 17 May 2016 04:36 |
Repository Staff Only: item control page
