Towards Separating Nondeterministic Time from Deterministic Time

It would be of interest to separate nondeterminism from determinism i. e. , to show that for all "nice" functions t(n), NTIME (t(n)), (the class of languages accepted by multitape nondeterministic Turing machines in time O(t(n))) strictly contains DTIME (t(n)) (the class of languages accepted by multitape deterministic Turing machines in time O(t(n)). We establish a weaker form of the statement. We show that there is a universal constant k such that for all "nice" functions t(n), the class of languages that can be accepted simultaneously in deterministic time O(t(n)) and space o((t(n))1/k) is strictly contained in NTIME (t(n)). (We will use the notation SPACE, TIME (s(n), t(n)) to denote the class of languages accepted by a deterministic TM in time O(t(n)) and simultaneously space O(s(n)).) This result is proved using a time-alternation trade-off and several other applications of this trade-off are presented. For example, we show that for each language L in SPACE, TIME (nl-ε, ni) (where o≪ε≪l, ε, i constants) there exists a j such that L is accepted by a O(n) time bounded alternating Turing machine with j alternations. The trade-off also leads to the separation ∪SεSt SPACE, TIME (s, t)⊂+Σ2 TIME(t) where t(n) is any "nice" function and St is a class of "nice" functions in o(t). Here St includes most natural functions for natural t. For example, nj/log*n is in Snj.

Authors

• Ravindran Kannan

Keywords

• Turing machines
• Mathematics
• Encoding
• Deterministic Time
• Functional Class
• Language Teaching
• Universal Constant
• Input Length
• Turing Machine
• Linear Time