DSPACE(n)NSPACE(n): A Degree Theoretic Characterization

摘要

It is shown that the following are equivalent. 1. DSPACE(n)=NSPACE(n). 2. There is a nontrivial ⩽1−NLm-degree that coincides with a ⩽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.