Time hierarchy theorem: Difference between revisions

Revision as of 16:38, 29 June 2005

Revision as of 04:32, 3 October 2005

Line 7:

===Statement===

For any time constructible function <math>t: N \rightarrow N</math>, there exists

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'')². In other words, the complexity class [[DTIME]](''f''(''n'')) is a strict subset of DTIME(''f''(''n'')²).

a language <math>A</math> that is decidable in time <math>O(t(n))</math> but not in time

<math>o(t(n)/\log t(n))</math>.

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''² but not time ''n'', since ''n'' is in o(''n''²/log ''n''²).

===Proof===

We prove this by constructing a Turing machine <math>B</math> that is a <math>O(t(n))</math>

We include here a proof that DTIME(''f''(''n'')) is a strict subset of DTIME(''f''(2''n'' + 1)³) as it is simpler. See the bottom of this section for information on how to extend the proof to ''f''(''n'')².

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>.

There are two parts to this construction. One part is to ensure that

To prove this, we first define a language as follows:

<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.

The basic structure of TM <math>B</math> is:

: <math> H_f = \left\{ ([M], x)\ |\ M \ \mbox{accepts}\ x \ \mbox{in}\ f(|x|) \ \mbox{steps} \right\} </math>

'''input''': string <math>w</math> with length <math>n</math>

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'').

'''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

Now we need to show that <math>B</math> halts within <math>O(t(n))</math> time. In order to

We know that we can decide membership of ''H_f'' 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'')³ operations, so

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>.

Formally we need to show that <math>A</math> is not decidable in <math>o(t(n)/\log

: <math> H_f \in \mathsf{TIME}(f(m)^3) </math>

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.

== Non-deterministic time hierarchy theorem ==

The rest of the proof will show that

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'')).

: <math> H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>

==Corollaries==

so that if we substitute 2''n'' + 1 for ''m'', we get the desired result. Let us assume that ''H_f'' is in this time complexity class, and we will attempt to reach a contradiction.

===Corrollary 1===

If ''H_f'' 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_f'' within <math> \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>.

''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)).''

This corollary shows that <math>t_1</math> and <math>t_2</math> belong to two different

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''&#39;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>.

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>).

===Corrollary 2===

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:

* 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_f'', 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_f'', and thus ''N'' '''does''' accept [''N''] in ''f''(''n'') steps. Contradiction!

''For any two real number <math>1 \leq \epsilon_1 < \epsilon_2</math>,

We thus conclude that the machine ''K'' does not exist, and so

TIME(<math>n^{\epsilon_1}</math>) <math>\subset</math> TIME(<math>n^{\epsilon_2}</math>)''

: <math> H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>

This corollary shows that polynomials of different degree are in

===Extension===

different TIME hierarchies and that the classes of the smaller degree

polynomials are strict subsets of the classes of the larger degree

polynomials.

===Corrollary 3===

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

: <math> H_f \in \mathsf{TIME}(f(m)^3) </math>

''<math>P \subset EXPTIME</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> H_f \in \mathsf{TIME}(f(m) \log f(m)) </math>

By this corollary, the classes of polynomial time algorithms and

but since this model of simulation is rather involved, it is not included here.

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==