Oracles for Deterministic Versus Alternating Classes
William I. Gasarch · SIAM Journal on Computing · 1987
We construct oracles that force all possible relationships between ${\textit{NP}}$ and ${\textit{EXP}}_K = {\textit{DTIME}}(2^{O(n^k )} )$. We generalize these results to obtain a theorem about oracles that force relationships between deterministic and nondeterministic (and alternating) classes, from which many corollaries follow. The corollaries are interesting because we compare a powerful type of machine (e.g., nondeterministic, alternating) to a less powerful type of machine that can use more time. One of our corollaries is that the result ${\textit{DTIME}}(n\log ^ * (n)) \subseteq \Sigma _2 - {\text{TIME}}(n)$ does not relativize.