DSPACE(N)=(QUESTIONABLE)NSPACE(N) - A DEGREE THEORETIC CHARACTERIZATION

Authors
AGRAWAL M
Citation
M. Agrawal, DSPACE(N)=(QUESTIONABLE)NSPACE(N) - A DEGREE THEORETIC CHARACTERIZATION, Journal of computer and system sciences, 54(3), 1997, pp. 383-392
Citations number
22
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
54
Issue
3
Year of publication
1997
Pages
383 - 392
Database
ISI
SICI code
0022-0000(1997)54:3<383:D-ADTC>2.0.ZU;2-8
Abstract
It is shown that the following are equivalent. 1. DSPACE(n) = NSPACE(n ). 2. There is a nontrivial less than or equal to(m)(1-NL)-degree that coincides with less than or equal to(m)(1-L)-degree. 3. For every cla ss C closed under log-lin reductions, the less than or equal to(m)(1-N L)-complete degree of C coincides with the less than or equal to(m)(1- L)-complete degree of C. (C) 1997 Academic Press.