<p>It is known that any problem that you can compute on a RAM machine in time $T(n)$, you can do it in a Turing Machine in time at most $T(n)^2$. You need to notice that the total size of the memory used can not be more than $T(n)$, since that would mean that you did more write operations than $T(n)$, so each time you fetch something from RAM memory, the Turing machine would take in the worst case $T(n)$ time to find the desired element sequentially from the tape. Besides memory access, the rest of operations should take around the same time. And thus you get the bound.</p>

CC BY-SA 3.0
2015-05-11T22:04:13.253Z
2015-05-11T22:04:13.253Z
Javier Cano
<p>Example below proves that an algorithm $A$ that takes $O(n\log(n))$ to solve a problem on word-Ram might need $O(n^2 \log(n)^3)$ on a <strong>1-tape Turing Machine (TM) that exactly executes all calculations indicated by $A$</strong>. I understand the question relates to the 1-tape TM, and I only use this one in my response. This is an edit to address the remarks of Emil Jeřábek.</p>

<p>We will find the <strong>following more general conclusion</strong>. To prove that the TM can solve in $O(T(n)^2)$ a problem solved in $O(T(n))$ by an algorithm $A$ on RAM, it is <strong>not</strong> enough run $A$ on the TM. A <em>clever</em> algorithm might be needed. Same applies if one wants to prove an $O(n\log(n))$ overhead. Proving the existence of a clever algorithm whenever needed seems far from immediate, to say the least. This is <em>not</em> in line with other responses that basically only propose to simulate/execute on the TM <em>all RAM calculations</em> (of algorithm $A$) to announce a TM complexity like $O(T(n)^2)$ or $O(T(n)n\log(n))$. </p>

<p><strong>Problem:</strong> We are given an array/table $\texttt{tab}$ with $n=2k$ integers each one stored on $\log(n)$ bits. We are given a second array $\texttt{d}$ with $\log(n)$ positions, each one recording a number of $\log(n)$ bits. For any $t\in[0..\log(n)-1]$, we define $X_t=1$ if $\texttt{tab}[i]$ MOD $\texttt{d}[t]=\texttt{tab}[n/2+i]$ MOD $\texttt{d}[t]~\forall i\in [0..n/2-1]$. Otherwise, $X_t=0$. Output $\sum_{t=0}^{\log(n)-1} X_t$. I consider the input is given as a tape with $n\log(n)+\log(n)\log(n)$ binary digits, to address the comments of Emil Jeřábek.</p>

<p><strong>Algorithm $A$ on RAM</strong> A RAM with word size $w=\log(n)$ needs $O(n\log(n)+\log(n)^2)$ = $O(n\log(n))$ to read the binary string input data. But after reading the data, it can work only with words of $\log(n)$ size. Algorithm $A$ calculates any $X_t$ in $O(n)$ by going through all $i\in [0..n/2-1]$ and testing the condition. The main loop of $A$ is <strong>FOR $t=0, 1, 2, \dots \log(n)-1$: calculate $X_t$</strong>. The total complexity is $O(n\log(n))$ (reading data) + $O(n\log(n))$ (doing the calculations), so $A$ can do it all in $O(n\log(n))$ on RAM.</p>

<p><strong>Algorithm $A$ on the 1-tape TM:</strong> I argue the one-tape TM needs $O(n^2 \log(n)^2)$ time for a fixed $t$. From the viewpoint of the TM, determining $A_t$ is equivalent to testing the equality of two binary strings of length $O(n\log(n))$. For instance, the MOD operation $\texttt{tab}[i]$ MOD $\texttt{d}[t]$ might be equivalent to removing bit $0$ of $\texttt{tab}[i]$. In such cases, determining $A_t$ is equivalent to equality testing on bit strings with of length $n(\log(n)-1)/2$. It is well-known that testing the equality of two strings of length $m$ requires $O(m^2)$ on the 1-tape TM, but I can not really find a reference right now. However, I provide a proof in ps. If the TM executes the <em>main loop</em> of $A$, it has to spend at least $O((n\log n)^2)$ for each $t=0, 1, 2, \dots \log(n)-1$, ending up in $O(n^2 \log(n)^3)$.</p>

<hr>

<p>ps. I show that equality-testing on bit strings with $m$ bits can <em>not</em> be
faster than palyndrome-testing on strings with $m$ bits (palyndrome is known to take at least $O(m^2)$ time). We can modify any TM
algorithm for equality-testing to solve palindrome. Assume the equality-testing
TM starts with two integers: one at left of the head, one at right (this is the
simplest input form for the TM). Each move over the left positions can be
mirrored (reflected) over the right positions. We build a mirrored TM: whenever
the initial TM is at a position $-x&lt;0$ (on the left), the mirrored TM is at position $x$ (on the right). If a
TM solved equality testing in less than $O(m^2)$, this modified mirrored TM
would solve palindrome in less than $O(m^2)$. </p>

<p>Also, there are some equality-testing TM algorithms out there and all of them require quadratic time because they need some zigzagging, see for instance the Turing Machine Example 2 at <a href="http://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec3.pdf" rel="nofollow noreferrer">courses.cs.washington.edu/courses/cse431/14sp/scribes/lec3.pdf</a></p>

CC BY-SA 3.0
2017-07-27T07:47:41.997Z
The lower bound for palindromes only holds for the unnatural single-tape model. It is straightforward to test equality of two strings on a TM in linear time. The same holds for equality of two sequences of longer entries. Also, in order for the question to make any sense at all, the inputs for both machine models must be identical, i.e., written as strings over a finite alphabet. Thus, your RAM would need time O(log n) to read each entry and convert it to a word, rendering this operation pointless.
Emil Jeřábek
CC BY-SA 3.0
2017-07-27T10:00:33.013Z
@Emil Jeřábek, I will edit my reply to indicate that I only think about the 1-tape TM. When you say a TM can test equality in linear time, I suppose you think to a 2-tape TM. However, I understood that the whole question is about 1-tape TMs. Regarding the input form, I must confess you might be right, at least for some word-RAMs. But as far as I know, a C++ int array stores the integers one after the other with no separator, as if they stored together a sequence of bits. 10 ints on 16 bits occupy exactly 160 bits, non? Even if this is not the case, one could build a machine working this way.
Daniel Porumbel
CC BY-SA 3.0
2017-07-27T12:03:35.697Z
The standard Turing machine model in complexity theory is multi-tape. I fail to see how C++ is of any relevance here, we are not discussing C++, but the RAM model. In this model, individual memory locations may hold numbers of length $O(\log n)$, but we can still operate only on one (or $O(1)$) memory location at a time. In particular, we can only access the input one location at a time: there is no operation that would allow you to do “read $\log n$ input locations and splice them together into a single word” in constant time.
Emil Jeřábek
CC BY-SA 3.0
2017-07-27T13:47:55.813Z
There are two possibilities: (1) Input location [0] contains the first bit of the first number, location [1] contains the second bit of the first number, and so on. Then it needs $O(n\log n)$ time to read on RAM, just like for a Turing machine. Thus, even with single-tape TMs, you only get a quadratic speed-up. (2) Input location [0] contains the first number, location [1] the second number, and so on. Then the problem is meaningless on a TM, as it can’t process input of this form. Thus, you don’t get any speed-up at all, but a problem that is only expressible in one of the machine models.
Emil Jeřábek
CC BY-SA 3.0
2017-07-29T12:40:44.223Z
@Emil Jeřábek, Following your remarks, I edited the question to propose a problem and a RAM algorithm that explicitly takes $O(n\log(n))$ to read the data (from a tape). I removed some of my remarks that are no longer relevant. I hope this solves the problem you pointed out.
Daniel Porumbel
CC BY-SA 3.0
2017-07-30T18:26:52.803Z
Your argument for the TM lower bound is fallacious. Even if for each $t$, the machine needs time $\Omega(n^2(\log n)^2)$, the only lower bound this gives on the overall computation time is still only $\Omega(n^2(\log n)^2)$, not $\Omega(n^2(\log n)^3)$. The TM does not need to proceed by doing the computation for each $t$ one after another, it may well use a completely different method that yields the final answer without separate intermediate results for each $t$.
Emil Jeřábek
CC BY-SA 3.0
2017-07-30T20:47:41.720Z
Ahh, yes, sorry. Thank you for the time you took on my response. I edited it again, generating a weaker conclusion: to prove that the TM solves in $O(T(n)^2)$ a problem solved in $O(T(n))$ by an algorithm $A$ on RAM, it is *not* enough to execute all calculations of $A$ on the TM (some other responses seemed to indicate this to me). Don't hesitate if you see other fallacies.
Daniel Porumbel
CC BY-SA 3.0
2017-07-26T22:06:42.333Z
2017-08-02T21:41:15.087Z
2017-08-02T21:41:15.087Z
Daniel Porumbel
<p>If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly interested if there are wide gaps for natural problems of general interest.</p>

CC BY-SA 3.0
2015-05-11T10:45:31.120Z
a RAM machine can be simulated by a Turing machine with overhead of $O(n\log n)$ in runtime. So there won't be really big gaps.
Shaull
CC BY-SA 3.0
2015-05-11T10:48:09.040Z
@Shaull Does a gap of that size exist for any natural/popular problem?
Simd
CC BY-SA 3.0
2015-05-11T10:50:36.917Z
It kind of depends on the exact model. If you assume that the RAM machine has natural numbers in its cells (and as input), then the problem of deciding if the input is the number $n$ would take $O(1)$ in a RAM machine, but $O(n\log n)$ in a TM.
Shaull
CC BY-SA 3.0
2015-05-11T16:54:00.400Z
Palindrome takes $\Omega(n^2)$ time on a single-tape TM (and is $O(n)$ in RAM).  http://www.eecs.yorku.ca/course_archive/2008-09/W/6115/palindrome.pdf
SamM
CC BY-SA 3.0
2015-05-11T17:47:10.210Z
Shaull's comment is only true for nondeterministic machines and in the two-tape TM setting, as far as I know. Citation, Shaull?
Ryan Williams
CC BY-SA 3.0
2017-07-30T22:59:31.943Z
I think MM is in $O(n^2)$ in RAM model but the record in tape model is at least $\omega(n^{2.35})$.
Turbo
CC BY-SA 3.0
2017-08-02T10:01:26.990Z
If RAM works in $T$ steps, then (deterministic) Turing can simulate in $T^3$ steps: Problem 8.6 in *Models of Computation* by Savage.
Radu GRIGore
CC BY-SA 4.0
2020-02-01T08:07:07.173Z
@Shaull I want to echo Ryan William's request for a citation, but with a ping.
qbt937
CC BY-SA 4.0
2020-02-01T08:10:17.323Z
@qbt937 - Wow, what a blast from the past :) I believe I didn't supply a citation because I didn't have one (nor do I have one now), and it may well be that Ryan Williams is correct.
Shaull
<cc.complexity-theory><ds.algorithms>
Big gaps between RAM and Turing machine complexity
Simd
# Big gaps between RAM and Turing machine complexity

(Asked by: username_0 on 2015-05-11)

If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly interested if there are wide gaps for natural problems of general interest.

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: a RAM machine can be simulated by a Turing machine with overhead of $O(n\log n)$ in runtime. So there won't be really big gaps.  
> **username_0**: @Shaull Does a gap of that size exist for any natural/popular problem?  
> **username_1**: It kind of depends on the exact model. If you assume that the RAM machine has natural numbers in its cells (and as input), then the problem of deciding if the input is the number $n$ would take $O(1)$ in a RAM machine, but $O(n\log n)$ in a TM.  
> **username_2**: Palindrome takes $\Omega(n^2)$ time on a single-tape TM (and is $O(n)$ in RAM).  http://www.eecs.yorku.ca/course_archive/2008-09/W/6115/palindrome.pdf  
> **username_3**: Shaull's comment is only true for nondeterministic machines and in the two-tape TM setting, as far as I know. Citation, Shaull?  
> **username_4**: I think MM is in $O(n^2)$ in RAM model but the record in tape model is at least $\omega(n^{2.35})$.  
> **username_5**: If RAM works in $T$ steps, then (deterministic) Turing can simulate in $T^3$ steps: Problem 8.6 in *Models of Computation* by Savage.  
> **username_6**: @Shaull I want to echo Ryan William's request for a citation, but with a ping.  
> **username_1**: @qbt937 - Wow, what a blast from the past :) I believe I didn't supply a citation because I didn't have one (nor do I have one now), and it may well be that Ryan Williams is correct.  

---

## 2 answers

### Answer by username_7 on 2015-05-11. Score: 8

It is known that any problem that you can compute on a RAM machine in time $T(n)$, you can do it in a Turing Machine in time at most $T(n)^2$. You need to notice that the total size of the memory used can not be more than $T(n)$, since that would mean that you did more write operations than $T(n)$, so each time you fetch something from RAM memory, the Turing machine would take in the worst case $T(n)$ time to find the desired element sequentially from the tape. Besides memory access, the rest of operations should take around the same time. And thus you get the bound.


---

### Answer by username_8 on 2017-07-26. Score: 1

Example below proves that an algorithm $A$ that takes $O(n\log(n))$ to solve a problem on word-Ram might need $O(n^2 \log(n)^3)$ on a **1-tape Turing Machine (TM) that exactly executes all calculations indicated by $A$**. I understand the question relates to the 1-tape TM, and I only use this one in my response. This is an edit to address the remarks of Emil Jeřábek.

We will find the **following more general conclusion**. To prove that the TM can solve in $O(T(n)^2)$ a problem solved in $O(T(n))$ by an algorithm $A$ on RAM, it is **not** enough run $A$ on the TM. A *clever* algorithm might be needed. Same applies if one wants to prove an $O(n\log(n))$ overhead. Proving the existence of a clever algorithm whenever needed seems far from immediate, to say the least. This is *not* in line with other responses that basically only propose to simulate/execute on the TM *all RAM calculations* (of algorithm $A$) to announce a TM complexity like $O(T(n)^2)$ or $O(T(n)n\log(n))$.

**Problem:** We are given an array/table $\texttt{tab}$ with $n=2k$ integers each one stored on $\log(n)$ bits. We are given a second array $\texttt{d}$ with $\log(n)$ positions, each one recording a number of $\log(n)$ bits. For any $t\in[0..\log(n)-1]$, we define $X\_t=1$ if $\texttt{tab}[i]$ MOD $\texttt{d}[t]=\texttt{tab}[n/2+i]$ MOD $\texttt{d}[t]~\forall i\in [0..n/2-1]$. Otherwise, $X\_t=0$. Output $\sum\_{t=0}^{\log(n)-1} X\_t$. I consider the input is given as a tape with $n\log(n)+\log(n)\log(n)$ binary digits, to address the comments of Emil Jeřábek.

**Algorithm $A$ on RAM** A RAM with word size $w=\log(n)$ needs $O(n\log(n)+\log(n)^2)$ = $O(n\log(n))$ to read the binary string input data. But after reading the data, it can work only with words of $\log(n)$ size. Algorithm $A$ calculates any $X\_t$ in $O(n)$ by going through all $i\in [0..n/2-1]$ and testing the condition. The main loop of $A$ is **FOR $t=0, 1, 2, \dots \log(n)-1$: calculate $X\_t$**. The total complexity is $O(n\log(n))$ (reading data) + $O(n\log(n))$ (doing the calculations), so $A$ can do it all in $O(n\log(n))$ on RAM.

**Algorithm $A$ on the 1-tape TM:** I argue the one-tape TM needs $O(n^2 \log(n)^2)$ time for a fixed $t$. From the viewpoint of the TM, determining $A\_t$ is equivalent to testing the equality of two binary strings of length $O(n\log(n))$. For instance, the MOD operation $\texttt{tab}[i]$ MOD $\texttt{d}[t]$ might be equivalent to removing bit $0$ of $\texttt{tab}[i]$. In such cases, determining $A\_t$ is equivalent to equality testing on bit strings with of length $n(\log(n)-1)/2$. It is well-known that testing the equality of two strings of length $m$ requires $O(m^2)$ on the 1-tape TM, but I can not really find a reference right now. However, I provide a proof in ps. If the TM executes the *main loop* of $A$, it has to spend at least $O((n\log n)^2)$ for each $t=0, 1, 2, \dots \log(n)-1$, ending up in $O(n^2 \log(n)^3)$.

---

ps. I show that equality-testing on bit strings with $m$ bits can *not* be
faster than palyndrome-testing on strings with $m$ bits (palyndrome is known to take at least $O(m^2)$ time). We can modify any TM
algorithm for equality-testing to solve palindrome. Assume the equality-testing
TM starts with two integers: one at left of the head, one at right (this is the
simplest input form for the TM). Each move over the left positions can be
mirrored (reflected) over the right positions. We build a mirrored TM: whenever
the initial TM is at a position $-x<0$ (on the left), the mirrored TM is at position $x$ (on the right). If a
TM solved equality testing in less than $O(m^2)$, this modified mirrored TM
would solve palindrome in less than $O(m^2)$.

Also, there are some equality-testing TM algorithms out there and all of them require quadratic time because they need some zigzagging, see for instance the Turing Machine Example 2 at [courses.cs.washington.edu/courses/cse431/14sp/scribes/lec3.pdf](http://courses.cs.washington.edu/courses/cse431/14sp/scribes/lec3.pdf)

> **Comments:**
> **username_9**: The lower bound for palindromes only holds for the unnatural single-tape model. It is straightforward to test equality of two strings on a TM in linear time. The same holds for equality of two sequences of longer entries. Also, in order for the question to make any sense at all, the inputs for both machine models must be identical, i.e., written as strings over a finite alphabet. Thus, your RAM would need time O(log n) to read each entry and convert it to a word, rendering this operation pointless.  
> **username_8**: @Emil Jeřábek, I will edit my reply to indicate that I only think about the 1-tape TM. When you say a TM can test equality in linear time, I suppose you think to a 2-tape TM. However, I understood that the whole question is about 1-tape TMs. Regarding the input form, I must confess you might be right, at least for some word-RAMs. But as far as I know, a C++ int array stores the integers one after the other with no separator, as if they stored together a sequence of bits. 10 ints on 16 bits occupy exactly 160 bits, non? Even if this is not the case, one could build a machine working this way.  
> **username_9**: The standard Turing machine model in complexity theory is multi-tape. I fail to see how C++ is of any relevance here, we are not discussing C++, but the RAM model. In this model, individual memory locations may hold numbers of length $O(\log n)$, but we can still operate only on one (or $O(1)$) memory location at a time. In particular, we can only access the input one location at a time: there is no operation that would allow you to do “read $\log n$ input locations and splice them together into a single word” in constant time.  
> **username_9**: There are two possibilities: (1) Input location [0] contains the first bit of the first number, location [1] contains the second bit of the first number, and so on. Then it needs $O(n\log n)$ time to read on RAM, just like for a Turing machine. Thus, even with single-tape TMs, you only get a quadratic speed-up. (2) Input location [0] contains the first number, location [1] the second number, and so on. Then the problem is meaningless on a TM, as it can’t process input of this form. Thus, you don’t get any speed-up at all, but a problem that is only expressible in one of the machine models.  
> **username_8**: @Emil Jeřábek, Following your remarks, I edited the question to propose a problem and a RAM algorithm that explicitly takes $O(n\log(n))$ to read the data (from a tape). I removed some of my remarks that are no longer relevant. I hope this solves the problem you pointed out.  
> **username_9**: Your argument for the TM lower bound is fallacious. Even if for each $t$, the machine needs time $\Omega(n^2(\log n)^2)$, the only lower bound this gives on the overall computation time is still only $\Omega(n^2(\log n)^2)$, not $\Omega(n^2(\log n)^3)$. The TM does not need to proceed by doing the computation for each $t$ one after another, it may well use a completely different method that yields the final answer without separate intermediate results for each $t$.  
> **username_8**: Ahh, yes, sorry. Thank you for the time you took on my response. I edited it again, generating a weaker conclusion: to prove that the TM solves in $O(T(n)^2)$ a problem solved in $O(T(n))$ by an algorithm $A$ on RAM, it is *not* enough to execute all calculations of $A$ on the TM (some other responses seemed to indicate this to me). Don't hesitate if you see other fallacies.  

---

