Abstract
We show that NSPACE(s(n)) ⊆ DTIME(n · O(1)s(n)). This improves the known bound of NSPACE(s(n)) ⊆ DTIME(n2 · O(l)s(n)) when the space is "small", namely, s(n) = o(logn). We use a simple encoding trick combined with an amortization argument.
Original language | English (US) |
---|---|
Pages (from-to) | 155-157 |
Number of pages | 3 |
Journal | Information Processing Letters |
Volume | 55 |
Issue number | 3 |
DOIs | |
State | Published - Aug 11 1995 |
Keywords
- Computational complexity
- Theory of computation
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications