DSPACE(n)=?NSPACE(n): a degree theoretic characterization

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


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