9
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • 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$ Jun 30, 2014 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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