10
$\begingroup$

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.

$\endgroup$
  • 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$ – Shaull May 11 '15 at 10:45
  • $\begingroup$ @Shaull Does a gap of that size exist for any natural/popular problem? $\endgroup$ – Lembik May 11 '15 at 10:48
  • $\begingroup$ 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. $\endgroup$ – Shaull May 11 '15 at 10:50
  • 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$ – SamM May 11 '15 at 16:54
  • 5
    $\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 Williams May 11 '15 at 17:47
7
$\begingroup$

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.

$\endgroup$
  • 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$ – user6973 Jul 27 '17 at 19:35
1
$\begingroup$

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

$\endgroup$
  • $\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$ – Emil Jeřábek Jul 27 '17 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$ – Daniel Porumbel Jul 27 '17 at 10:00
  • 2
    $\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$ – Emil Jeřábek Jul 27 '17 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$ – Emil Jeřábek Jul 27 '17 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$ – Daniel Porumbel Jul 29 '17 at 12:40

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.