In the Arora-Barak book, in the definition of time constructible functions, it is said that using functions that are not time constructible can lead to "anomalous results". Does anyone have an example of such an "anomalous result"? I have heard in particular that there might exist functions such that the time hierarchy theorem does not hold, does anyone have an example of such functions? Is there something about this somewhere in the litterature?
Asked
Active
Viewed 470 times
10
-
3Have you had a look at these: http://math.stackexchange.com/questions/51082/definition-of-time-constructible-function and http://cstheory.stackexchange.com/questions/992/an-explicit-separation-between-time-constructibility-and-space-constructibility ? – Jukka Suomela Oct 11 '11 at 21:59
-
@JukkaSuomela: Yes I have, but they are about which functions are time/space constructible and why they are useful. – Pascal Oct 12 '11 at 06:30
2 Answers
11
Borodin's Gap Theorem: For every total computable function $g(n) \geq n$, there is a total computable function $t$ such that $DTIME[g(t(n))] = DTIME[t(n)]$.
In fact, this holds for any Blum complexity measure in place of $DTIME$.
See also the wikipedia page and references therein.
Joshua Grochow
- 37,260
- 4
- 129
- 228
6
Since the Wikipedia article doesn't give the proof and the paper is on ACM DL I thought that it might be useful to post the proof here:
THEOREM 3.7. (Gap Theorem).
Let $\Phi$ be a complexity measure, $g$ a nondecreasing recursive function such that $\forall x, g(x) \geq x$. Then there exists an increasing recursive function $t$ such that functions computable of complexity measure $t$ are the same as functions computable of complexity measure $g\circ t$.
PROOF.
Define $t$ as follows:
$$t(0) := 1$$ $$t(n) := \mu{ k > t(n-1)}: \forall i \leq n, (\Phi_i(n)<k \lor \Phi_i(n)> g(k) )$$
for all $n$, there is a $k$, since for all $i \leq n$:
a. if $\Phi_i(n)$ is undefined then $\forall k, \Phi_i(n)>g(k)$, and
b. if $\Phi_i(n)$ defined then $\exists k, \Phi_i(n) < k$.
$k$ can be found recursively, since $\Phi$ is a complexity measure and thus $\Phi_i(n) <k$ and $\Phi_i(n) > g(k)$ are recursive predicates.
$t$ satisfies the theorem, since $n \geq i$ implies that either $\Phi_i(n) < t(n)$ or $\Phi_i(n) > g \circ t(n)$.
QED.
We observe that an arbitrarily large $t$ can be found to satisfy Theorem 3.7. Suppose we want $t(n) > r(n)$, then define
$$t(0) := r(0) + 1$$ $$t(n) := \mu{k > max\{t(n-1), r(n)\}}: \ldots$$
(from Allan Borodin, "Computational complexity and the existence of complexity gaps", JACM 1972, with slight modifications.)
-
The idea is to define $t(n)$ to be the least $k$ s.t. any function (of index less than $n$) that is computable in complexity measure $g(k)$ is also computable in complexity measure $k$. – Kaveh Oct 13 '11 at 07:47