A note on improved deterministic time simulation of nondeterministic space for small space

Ee Chien Chang, Chee Yap

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)155-157
Number of pages3
JournalInformation Processing Letters
Volume55
Issue number3
DOIs
StatePublished - Aug 11 1995

Keywords

  • Computational complexity
  • Theory of computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A note on improved deterministic time simulation of nondeterministic space for small space'. Together they form a unique fingerprint.

  • Cite this