Agrawal, Manindra (2002) For completeness, sublogarithmic space is no space Information Processing Letters, 82 (6). pp. 321-325. ISSN 0020-0190
![]()
|
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