Content deleted Content added
removing my bogus comment |
THE PROOF! ... please proofread and everything! |
||
Line 3:
Both theorems use the notion of a '''time-constructible function'''. A [[function]] ''f'' : '''N''' → '''N''' is time-constructible if there exists a deterministic [[Turing machine]] such that for every ''n'' in '''N''', if the machine is started with an input of ''n'' ones, it will halt after precisely ''f''(''n'') steps. All [[polynomial]]s with non-negative integral coefficients are time-constructible, as are exponential functions such as 2<sup>''n''</sup>.
===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 determininstic 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>).▼
▲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 determininstic time ''f''(''n'')<sup>2</sup>. In other words, the complexity class
The proof is not constructive and uses a diagonalization argument.
As a consequence, one can show that the class [[Complexity classes P and NP|'''P''']] is a strict subset of [[EXPTIME]].
===Proof===
We include here a proof that TIME(''f''(''n'')) is a strict subset of TIME(''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>.
To prove this, we first define a language as follows:
: <math> H_f = \left\{ ([M], x)\ |\ M \ \mbox{accepts}\ x \ \mbox{in}\ f(|x|) \ \mbox{steps} \right\} </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'').
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
: <math> H_f \in \mathsf{TIME}(f(m)^3) </math>
The rest of the proof will show that
: <math> H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>
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.
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>.
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>.
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<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
: <math> H_f \notin \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )) </math>
===Extension===
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>
It is possible to find a provably more efficient model of simulation that establishes that
: <math> H_f \in \mathsf{TIME}(f( \left\lfloor m/2 \right\rfloor )^2) </math>
but since this model of simulation is rather involved, it is not included here.
=== Non-deterministic time hierarchy theorem ===
| |||