TY - JOUR
T1 - Downward translations of equality
AU - Allender, Eric
AU - Wilson, Christopher
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 1990/10/1
Y1 - 1990/10/1
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=0025508298&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025508298&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(90)90099-4
DO - 10.1016/0304-3975(90)90099-4
M3 - Article
AN - SCOPUS:0025508298
VL - 75
SP - 335
EP - 346
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 3
ER -