Problem Detail: 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.
Asked By : Andrew Ryzhikov
Answered By : Pys
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24361 Ask a Question Download Related Notes/Documents
