Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers in time $f(n)$, then there is a $7$-string Turing machine $M$, which computes $\phi$ in time $O(f(n)^3)$.

Consider the following example: $\phi(S)$ is a sum of first two numbers of a finite sequence $S$, or $0$, if $|S| < 2$. It seems to me that a RAM, defined in Papadimitriou's book computes $\phi$ in time $O(1)$. Thought, any Turing machine, computing $\phi$, should work for at least linear time (we can take an input of length $n$ with only two numbers in sequence). I don't see how to cope with this contradiction.

Could you please describe me, where I am wrong? Thanks a lot.

  • $\begingroup$ Try to follow the proof of Theorem 2.5 applied to your function $\phi(S)$ and see what (if anything) goes wrong. $\endgroup$ – Yuval Filmus May 4 '14 at 0:44

You're right, there is a missing assumption that f(n) is at least O(n). Indeed, the last line of the proof state that the operand are of size O(f(n)), while what has been proven before is O(f(n)+l(I)+l(B)). Since l(I) is O(n), the hypothesis is needed for this simplification.

| cite | improve this answer | |
  • 1
    $\begingroup$ What do you mean by "at least $O(n)$"? "At least" gives a lower bound; $O(\cdot)$ gives an upper bound. "At least something smaller than $n$" actually gives no information. $\endgroup$ – David Richerby Jun 30 '14 at 13:42

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.