Downward Translations of Equality
Christopher Wilson
Committee:
Technical Report(Aug 1988)
Keywords:

The main theorem of this paper gives a general technique for constructing an oracle which separates a deterministic and nondeterministic complexity class while the classes at a higher level are equal. As a corollary of the main theorem we obtain a result in [Book, Wilson, Xu, "Relativizing Time, Space, and Time-Space," SIAM J. Comput., 11(3), 1982, 571-581) that there is an oracle A such that PANPA yet DEXTA = NEXTA. Another corollary is that for some oracle A, DTIMEA(O(n))NTIMEA(O(n)) and DTIMEA(n2) = NTIMEA(n2). Some connections with sparse sets are then discussed.