A function t is time-constructible if there is a Turing machine M such that on input 1^{n} outputs 1^{t(n)} in time O(t(n)). Space constructible functions are defined similarly. All the natural functions are time and space constructible.
DTIME(t(n)) are the set of problems computable by a multi-tape Turing machine in deterministic time O(t(n)) on inputs of length n. NTIME (nondeterministic time), DSPACE and NSPACE are defined similarly.
Let t_{1} and t_{2} be time-constructible functions and s_{1} and s_{2} space-constructible function. We let "⊂" denote strict subset. A function f(n)=o(g(n)) if lim_{n→∞}f(n)/g(n)=0.
- If t_{1}(n)log t_{1}(n)=o(t_{2}(n)) then DTIME(t_{1}(n))⊂DTIME(t_{2}(n)).
- If t_{1}(n+1)=o(t_{2}(n)) then NTIME(t_{1}(n))⊂NTIME(t_{2}(n)).
- If s_{1}(n)=o(s_{2}(n)) then DSPACE(s_{1}(n))⊂DSPACE(s_{2}(n)).
- If s_{1}(n)=o(s_{2}(n)) then NSPACE(s_{1}(n))⊂NSPACE(s_{2}(n)).
Straightforward diagonalization does not work directly for nondeterministic computation because one need to negate the answer. For NSPACE we easily get around this problem by using Immerman-Szelepcsényi.
The NTIME hierarchy has the most interesting proof that leads to requiring the "+1" in t_{1}(n+1). This can make a big difference for t_{1}(n) larger than 2^{n2}.
An NTIME hierarchy was first proved by Cook and in the strongest form by Seiferas, Fischer and Meyer. We sketch a simple proof due to Zàk.
Let M_{1},… be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w=1^{i}01^{m}01^{k}:
- If k<m^{t1(m)} then simulate M_{i} on input 1^{i}01^{m}01^{k+1} for t_{2}(|w|) steps.
- If k=m^{t1(m)} then accept if 1^{i}01^{m}0 rejects which we can do quickly as a function of the current input size.
Since t_{1}(n+1)=o(t_{2}(n)) we have for sufficiently large m,
Dear Lance,
ReplyDeleteI always see these results in the first few sections of any complexity text. I am curious about other resuts that use the Hierarchy Theorems. For example, the DTIME hierarchy shows that P is a proper subset of EXP. What else can be said with these theorems? They seem quite applicable, and it would be nice to know about other results stem from them. Also, maybe you could do a post on the Polynomial Hierarchy since I have yet to find a lucid explanation of what that is all about. Thanks!
Steve Orzel
phloam@myrealbox.com
I'm curious about the log t1(n) term in the DTIME hierarchy. Is this a tight bound, or is it open as to whether this term can be reduced or eliminated? Sipser mentions in passing that this is an open question, but he used a 1-tape TM model in his exposition. I understand that if the number of tapes are fixed for some k >= 2, that the log t1(n) term can be eliminated altogether [Furer 1982].
ReplyDeleteActually, the name should by (in Tex) \v{Z}\'{a}k (hacek over Z is missing). The Czech language is strange:-)
ReplyDelete