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.
-
6$\begingroup$ 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. $\endgroup$– ShaullCommented May 11, 2015 at 10:45
-
$\begingroup$ @Shaull Does a gap of that size exist for any natural/popular problem? $\endgroup$– SimdCommented May 11, 2015 at 10:48
-
3$\begingroup$ Palindrome takes $\Omega(n^2)$ time on a single-tape TM (and is $O(n)$ in RAM). eecs.yorku.ca/course_archive/2008-09/W/6115/palindrome.pdf $\endgroup$– SamMCommented May 11, 2015 at 16:54
-
6$\begingroup$ Shaull's comment is only true for nondeterministic machines and in the two-tape TM setting, as far as I know. Citation, Shaull? $\endgroup$– Ryan WilliamsCommented May 11, 2015 at 17:47
-
1$\begingroup$ @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. $\endgroup$– ShaullCommented Feb 1, 2020 at 8:10
2 Answers
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.
-
2$\begingroup$ RAMs can compute the input's length (and thus also the party of that length) in logarithmic time, but basic Turing Machines need linear time to compute that parity. $\endgroup$– user6973Commented Jul 27, 2017 at 19:35
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
-
$\begingroup$ 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. $\endgroup$ Commented Jul 27, 2017 at 7:47
-
$\begingroup$ @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. $\endgroup$ Commented Jul 27, 2017 at 10:00
-
3$\begingroup$ 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. $\endgroup$ Commented Jul 27, 2017 at 12:03
-
$\begingroup$ 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. $\endgroup$ Commented Jul 27, 2017 at 13:47
-
$\begingroup$ @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. $\endgroup$ Commented Jul 29, 2017 at 12:40