Agrawal, M. (1995) DSPACE(n)=?NSPACE(n): a degree theoretic characterization Proceedings of Tenth Annual IEEE Structure in Complexity Theory Conference . pp. 315-323. ISSN 1063-6870
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnum...
Related URL: http://dx.doi.org/10.1109/SCT.1995.514869
Abstract
It is shown that the following are equivalent: 1. DSPACE(n)=NSPACE(n). 2. There is a ⩽m1-NL-degree that coincides with a ⩽m1-L degree. 3. For every class C closed under logspace reductions the ⩽m1-NL-complete degree of C coincides with the ⩽m1-L-complete degree of C.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to IEEE. |
| ID Code: | 95351 |
| Deposited On: | 07 Nov 2012 04:49 |
| Last Modified: | 07 Nov 2012 04:50 |
Repository Staff Only: item control page
