| Time Hierarchy Theorem |
Article Index for Time |
Website Links For Time |
Information AboutTime Hierarchy Theorem |
| CATEGORIES ABOUT TIME HIERARCHY THEOREM | |
| computational complexity theory | |
| mathematical theorems | |
|
BACKGROUND Both theorems use the notion of a 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''n''. PROOF OVERVIEW We need to prove that some time class TIME(''g(n)'') is strictly larger than some time class TIME(''f(n)''). We do this by constructing a machine which cannot be in TIME(''f(n)''), by Diagonalization . We then show that the machine is in TIME(''g(n)''), using a Simulator Machine . DETERMINISTIC TIME HIERARCHY THEOREM Statement The theorem states that: 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'')2. In other words, the complexity class DTIME (''f''(''n'')) is a strict subset of DTIME(''f''(''n'')2). Note that ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible. 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''2 but not time ''n'', since ''n'' is in o(''n''2/log ''n''2). Proof We include here a proof that DTIME(''f''(''n'')) is a strict subset of DTIME(''f''(2''n'' + 1)3) as it is simpler. See the bottom of this section for information on how to extend the proof to ''f''(''n'')2. To prove this, we first define a language as follows: |
|
|