Agrawal, Manindra (1997) DSPACE(n)=2 NSPACE(n): a degree theoretic characterization Journal of Computer and System Sciences, 54 (3). pp. 383-392. ISSN 0022-0000
![[img]](http://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Publisher Version
198kB |
Official URL: http://linkinghub.elsevier.com/retrieve/pii/S00220...
Related URL: http://dx.doi.org/10.1006/jcss.1997.1483
Abstract
It is shown that the following are equivalent. 1. DSPACE(n)=NSPACE(n). 2. There is a nontrivial ≤ 1-NLm-degree that coincides with ≤1-Lm-degree. 3. For every class C closed under log-lin reductions, the ≤1-NLm-complete degree of C coincides with the ≤1-Lm-complete degree of C.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 20225 |
| Deposited On: | 20 Nov 2010 14:49 |
| Last Modified: | 17 May 2016 04:36 |
Repository Staff Only: item control page
