Downward translations of equality

Eric Allender, Christopher Wilson

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

In this paper we construct oracles relative to which DTIME(T(n)) equals NTIME(T(n)) and DTIME(t(n)) does not equal NTIME (t(n)), for t(n) sufficiently smaller than T(n). A stronger result than this is also obtained, though for fewer T(n), expressedin two parts. For T(n)≤2n, there is an oracle relative to which DTIME(T(n)) equals NTIME(T(n)) and NTIME(2n) contains a set not in DTIME(t(n)) for any t(n) growing more slowly than T(n). For T(n)≤22n+0(1), there is an oracle relative to which DTIME(T(n)) equals NTIME(T(n)) and NTIME(log T(n)) contains a set not in DTIME(t(n)) for t(n) growing more slowly than T(n). These results expand on those obtained by Dekhtyar (1976), Book et al. (1982), and Allender (1989).

Original languageEnglish (US)
Pages (from-to)335-346
Number of pages12
JournalTheoretical Computer Science
Volume75
Issue number3
DOIs
StatePublished - Oct 1 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Downward translations of equality'. Together they form a unique fingerprint.

  • Cite this