10
$\begingroup$

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?

$\endgroup$
2
11
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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

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

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

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Kaveh
    Oct 13 '11 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.