### 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)≤2^{n}, 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)≤2^{2n+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 language | English (US) |
---|---|

Pages (from-to) | 335-346 |

Number of pages | 12 |

Journal | Theoretical Computer Science |

Volume | 75 |

Issue number | 3 |

DOIs | |

State | Published - 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

*Theoretical Computer Science*,

*75*(3), 335-346. https://doi.org/10.1016/0304-3975(90)90099-4