|
===Statement===
If ''f''(''n'') is a time-constructible function, then there exists a [[decision problem]] which cannot be solved in worst-case deterministic time ''f''(''n'') but can be solved in worst-case deterministic time ''f''(''n'')<sup>2</sup>. In other words, the complexity class [[DTIME]](''f''(''n'')) is a strict subset of DTIME(''f''(''n'')<sup>2</sup>).
For any [[time constructible]] function <math>t: N \rightarrow N</math>, there exists
a language <math>A</math> that is decidable in time <math>O(t(n))</math> but not in time
Even more generally, it can be shown that if ''f''(''n'') is time-constructible, then DTIME(o(''f''(''n'')/log ''f''(''n''))) is properly contained in DTIME(''f''(''n'')). For example, there are problems solvable in time ''n''<sup>2</sup> but not time ''n'', since ''n'' is in o(''n''<sup>2</sup>/log ''n''<sup>2</sup>).
<math>o(t(n)/\log t(n))</math>.
===Proof===
We include here a proof that DTIME(''f''(''n'')) is a strict subset of DTIME(''f''(2''n'' + 1)<sup>3</sup>) as it is simpler. See the bottom of this section for information on how to extend the proof to ''f''(''n'')<sup>2</sup>.
We prove this by constructing a Turing machine <math>B</math> that is a <math>O(t(n))</math>
decider for a language <math>A</math> that is not decidable in <math>o(t(n)/\log
t(n))</math> time. In order to ensure that <math>B</math> finishes its computation in
time <math>O(t(n))</math> we include in <math>B</math> a counter of length <math>\log t(n)</math>,
which is the number of bits required to store the number <math>O(t(n))</math>.
To prove this, we first define a language as follows:
There are two parts to this construction. One part is to ensure that
<math>B</math> has a different output from all <math>o(t(n)/\log t(n))</math> Turing
machines. We do this by simulating a given Turing machine <math>M</math> on
input <math>\langle M\rangle 10^*</math>. If <math>M</math> finishes its computation
quickly enough (in time less than <math>t(n)/\log t(n)</math> where <math>n</math> is the
length of the input string), we construct <math>B</math> to have the opposite
output (this is similar to the digitalisation technique explained in the [[Diagonalization Lemma]]). But what if <math>M</math> does not halt in the alloted time? we still need
to make sure that <math>B</math> is a <math>O(t(n))</math> decider, so we add a counter to
<math>B</math> to make sure that it stops after <math>t(n)</math> steps.
: <math> H_f = \left\{ ([M], x)\ |\ M \ \mbox{accepts}\ x \ \mbox{in}\ f(|x|) \ \mbox{steps} \right\} </math>
The basic structure of TM <math>B</math> is:
Here, ''M'' is a deterministic Turing machine, and ''x'' is its input (the initial contents of its tape). [''M''] denotes an input that encodes the Turing machine ''M''. Let ''m'' be the size of the tuple ([''M''], ''x'').
'''input''': string <math>w</math> with length <math>n</math>
'''if''' w 6 <math>w \not= \langle M\rangle 10^*</math> for some TM M '''then'''
reject
'''end if'''
calculate <math>\lceil t(n) / \log t(n)\rceil</math> and use this value to create counter <math>c</math>
'''while c > 0 do'''
simulate <math>M</math> with input <math>w</math> for 1 step
'''if''' <math>M</math> accepts '''then'''
reject
'''else if''' <math>M</math> rejects '''then'''
accept
'''end if'''
decrement <math>c</math>
'''end while'''
reject
We know that we can decide membership of ''H<sub>f</sub>'' by way of a deterministic Turing machine that first calculates ''f''(|''x''|), then writes out a row of 0s of that length, and then uses this row of 0s as a "clock" or "counter" to simulate ''M'' for at most that many steps. At each step, the simulating machine needs to look through the definition of ''M'' to decide what the next action would be. It is safe to say that this takes at most ''f''(''m'')<sup>3</sup> operations, so
Now we need to show that <math>B</math> halts within <math>O(t(n))</math> time. In order to
simulate <math>M</math>, <math>B</math> needs to keep track of <math>M</math>'s state, the tape symbol
<math>M</math> is currently reading, and <math>M</math>'s transition function. If <math>B</math> were
to store this information in one spot on its tape, as <math>B</math> simulates
<math>M</math> <math>B</math> may have to spend an arbitrary amount of time moving traveling
back and forth retrieving this information about <math>M</math>. So we introduce
a notion of tracks on <math>B</math>'s tape. In one track we will store
information about <math>M</math>, in the other track we will store information
about <math>B</math>'s current computation. We change <math>B</math>'s tape alphabet to a
set of pairs, one from each track. Then, in a constant amount of time
(dependent on the length of <math>M</math>, not the length of the entire input
string <math>w</math>) <math>B</math> can copy the information on the first track to the
current ___location on the second track. So, if <math>M</math> runs in time <math>g(n)</math>,
<math>B</math> can simulate it in time <math>O(g(n))</math>. We add the counter to a third
tape (also to cut down on unbounded time of traveling between the
current head position of <math>B</math> and the clock). The actual clock
updating operations require only <math>O(\log t(n))</math> because the length of
the clock is <math>\log (t(n) / \log t(n))</math>. So, if we allow <math>B</math> to
execute for <math>\lceil t(n) / \log t(n)\rceil</math> steps and each step
requires <math>O(\log t(n))</math> time, <math>B</math> will halt in time <math>O(t(n))</math>.
: <math> H_f \in \mathsf{TIME}(f(m)^3) </math>
Formally we need to show that <math>A</math> is not decidable in <math>o(t(n)/\log
t(n))</math> time. We prove this by contradiction. Assume that TM <math>M</math>
decides <math>A</math> in time <math>g(n)</math>, which is <math>o(t(n)/\log t(n))</math>. Then <math>B</math>
can simulate <math>M</math> in <math>d \cdot g(n)</math> time for some constant <math>d</math>. So,
for some constant <math>n_0</math>, <math>d \cdot g(n) < t(n) / \log t(n)</math> for all <math>n
\geq n_0</math>. Consider what happens when we run <math>B</math> on input <math>\langle
M\rangle 10^{n_0}</math>. This input is longer than <math>n_{0}</math>, which means
that <math>B</math> will have time to simulate <math>M</math> until it halts and then <math>B</math>
will do the opposite of <math>M</math> on the same input. Thus, <math>M</math> does not
decide <math>A</math> which contradicts our assumption. So, <math>A</math> is not decidable
in <math>o(t(n)/\log t(n))</math> time.
The rest of the proof will show that
== Non-deterministic time hierarchy theorem ==
: <math> H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>
If ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Big O notation|o]](''g''(''n'')), then there exists a decision problem which cannot be solved in non-deterministic time ''f''(''n'') but can be solved in non-deterministic time ''g''(''n''). In other words, the complexity class [[NTIME]](''f''(''n'')) is a strict subset of NTIME(''g''(''n'')).
so that if we substitute 2''n'' + 1 for ''m'', we get the desired result. Let us assume that ''H<sub>f</sub>'' is in this time complexity class, and we will attempt to reach a contradiction.
==Corollaries==
If ''H<sub>f</sub>'' is in this time complexity class, it means we can construct some machine ''K'' which, given some machine description [''M''] and input ''x'', decides whether the tuple ([''M''], ''x'') is in ''H<sub>f</sub>'' within <math> \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>.
===Corrollary 1===
''For any two functions <math>t_1</math>, <math>t_2: \mathbb{N} \longrightarrow
\mathbb{N}</math>, where <math>t_1</math>(n) is o(<math>t_2</math>(n)/<math>log t_2</math>(n)) and <math>t_2</math> is
time constructible, TIME(<math>t_1</math>(n)) <math>\subset</math> TIME(<math>t_2</math>(n)).''
Therefore we can use this ''K'' to construct another machine, ''N'', which takes a machine description [''M''] and runs ''K'' on the tuple ([''M''], [''M'']), and then accepts only if ''K'' rejects, and rejects if ''K'' accepts. If now ''n'' is the length of the input to ''N'', then ''m'' (the length of the input to ''K'') is twice ''n'' plus some delimiter symbol, so ''m'' = 2''n'' + 1. ''N'''s running time is thus <math> \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) = \mathsf{TIME}(f( \left\lfloor (2n+1)/2 \right\rfloor )) = \mathsf{TIME}(f(n)) </math>.
This corollary shows that <math>t_1</math> and <math>t_2</math> belong to two different
classes of TIME hierarchies (and that TIME(<math>t_2</math>) includes
TIME(<math>t_1</math>). Note that we can say the two classes are different
because TIME(<math>t_1</math>) is a strict subset of TIME(<math>t_2</math>).
Now if we feed [''N''] as input into ''N'' itself (which makes ''n'' the length of [''N'']) and ask the question whether ''N'' accepts its own description as input, we get:
===Corrollary 2===
* If ''N'' '''accepts''' [''N''] (which we know it does in at most ''f''(''n'') operations), this means that ''K'' '''rejects''' ([''N''], [''N'']), so ([''N''], [''N'']) is not in ''H<sub>f</sub>'', and thus ''N'' does not accept [''N''] in ''f''(''n'') steps. Contradiction!
* If ''N'' '''rejects''' [''N''] (which we know it does in at most ''f''(''n'') operations), this means that ''K'' '''accepts''' ([''N''], [''N'']), so ([''N''], [''N'']) '''is''' in ''H<sub>f</sub>'', and thus ''N'' '''does''' accept [''N''] in ''f''(''n'') steps. Contradiction!
We thus conclude that the machine ''K'' does not exist, and so
''For any two real number <math>1 \leq \epsilon_1 < \epsilon_2</math>,
: <math> H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>
TIME(<math>n^{\epsilon_1}</math>) <math>\subset</math> TIME(<math>n^{\epsilon_2}</math>)''
===Extension===
This corollary shows that polynomials of different degree are in
different TIME hierarchies and that the classes of the smaller degree
polynomials are strict subsets of the classes of the larger degree
polynomials.
The reader may have realised that the proof is simpler because we have chosen a simple Turing machine simulation for which we can be certain that
===Corrollary 3===
: <math> H_f \in \mathsf{TIME}(f(m)^3) </math>
It has been shown [http://www.cs.berkeley.edu/~luca/cs172/noteh.pdf] that a more efficient model of simulation exists which establishes that
''<math>P \subset EXPTIME</math>''
: <math> H_f \in \mathsf{TIME}(f(m) \log f(m)) </math>
but since this model of simulation is rather involved, it is not included here.
By this corollary, the classes of polynomial time algorithms and
exponential time algorithms are different.
== Non-deterministic time hierarchy theorem ==
If ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Big O notation|o]](''g''(''n'')), then there exists a decision problem which cannot be solved in non-deterministic time ''f''(''n'') but can be solved in non-deterministic time ''g''(''n''). In other words, the complexity class [[NTIME]](''f''(''n'')) is a strict subset of NTIME(''g''(''n'')).
==Consequences==
| 