Some results on relativized deterministic and nondeterministic time hierarchies

摘要

Relativized forms of deterministic and nondeterministic time complexity classes are considered. It is shown, at variance with recently published observations, that one basic step by step simulation technique in complexity theory does not relativize (i.e., does not generalize to computations with oracles), using the current definitions for time and space complexity of oracle computations. A new natural definition is given with respect to which this simulation does relativize. Further results in the paper are obtained with respect to this new definition. It is shown that for each “well-behaved” class of functions, τ, there is a set E such that for each function t(n) ϵ τ, there is a set which is accepted in t(n) time by a nondeterministic Turing machine with oracle E, but is not accepted in less than O(2t(n)) time by any deterministic Turing machine with oracle E, and there is another set which is accepted in t(n) time by a deterministic Turing machine with oracle E, but is not accepted in less than O(t(n)) time by any nondeterministic Turing machine with oracle E. The techniques used are based on refinements of diagonalization techniques of Baker et al. (SICOMP (1975), 421–442) and Ladner and Lynch (Math. Systems Theory 10 (1976), 19–32). One immediate corollary is a generalization of a theorem of Baker et al. (SICOMP (1975), 421–442), which asserts that for some set E, PE ≠ NPE. Other applications concerning deterministic and nondeterministic relativized time hierarchies are given.