exponentially different running times random-access machine (RAM) vs Turing machine

Question

I propose a simple polynomial algorithm for the following problem. Given $m$ integers each one stored on $n$ bits, output the integer that appears the most often.

1. Reserve a memory area with $2^n$ slots/registers/locations/cells, each cell being long enough to store the number $m$. This requires constant time because we do not initialize/touch the cells. If you agree with this, skip to step 2. Otherwise, check the following four points.
   • One could easily be tempted to read "reserve a memory area" as "allocate a memory area". Actually, the memory allocation operation is an invention/complication of real multi-tasking machines where programs can "fight" for memory. If I consider some (Random Access Machine) RAM machine that only knows running my algorithm, I can state that the algorithm can simply use the whole memory. Thus, it is enough to reserve (read "put aside" not "allocate") the first $2^n$ cells for a an array with $2^n$ elements. The next memory cells are simply used for other variables.
   • To be more precise, I consider running my algorithm on a RAM-TM (Random Access Memory-Turing Machine) that is multi-tape TM with a memory and an index tape. Given a number written on the index tape, the RAM-TM takes constant time to move the head of the memory tape to the location indicated on the index tape. We also allow the RAM-TM to have a few other tapes for easily doing arithmetics. The RAM-TM has no notion of memory allocation. This seems to be a simplification of the various (Transdichotomous or word) RAM machines out there.
   • Even if I must confess I do not really know the exact technical details of all theoretical machines RAM (or RASP), it is possible to work with an exponentially-large memory area and yet use only a polynomially large number of cells and my algorithm is not the first doing this. This also happens in the binary search algorithm over a sorted array: $n$ cells but only $O(log(n))$ time complexity. This scientific paper introduced a data structure that uses a large memory area but has constant time access, see also the answer of zotachidil to this question. My algorithm could work with this data structure instead of explicitly reserving space.
   • see Ps 1.
2. Go through the $m$ numbers in the input and for each one of them $x$ assign $[x]=0$, where $[x]$ is the memory slot/location number $x$ in the above reserved memory area.
3. Go through the $m$ numbers in the input and for each one of them $x$ assign $[x]=[x]+1$.
4. Take the first number $x$ in the input and assign $outVal=x$ and $maxFreq=[x]$.
5. Scan again the $m$ numbers and for each number $x$ perform: if $[x]>maxFreq$, set $outVal=x$ and $maxFreq=[x]$.
6. Output $outVal$.

The algorithm has time complexity $O(mn)$ assuming $n\hskip 0.7mm \not \hskip -0.7mm \ll m$ at least on the RAM-TM (see ps 2.), i.e., linear. It is certainly not the only algorithm to solve the problem, but I do not know any other linear algorithm using polynomial memory.

However, the big problem is that the algorithm would require exponential time in a Turing machine, no? Does this contradict one of the Extended/Complexity-Theoretic Church–Turing Theses? The section "Variations" of the Wikipedia article on the Church–Turing thesis states that "polynomial-time overhead and constant-space overhead could be simultaneously achieved for a simulation of a Random Access Machine on a Turing machine [55]", where [55] is "C. Slot, P. van Emde Boas, On tape versus core: an application of space efficient perfect hash functions to the invariance of space, STOC, December 1984". Something seems inconsistent. Any help would be greatly appreciated.

ps 1. A real-machine argument for the fact one can allocate $O(2^n)$ bits in constant time. Notice I did not say the $2^n$ cells are initialized to some zero values. In a programming language like C this should be achieved by an instruction malloc instead of calloc. In my comment to D.W.'s answer, I provide a reference for a real-life memory allocator that "performs the allocation/deallocation in constant time". However, D.W. seem to reject this argument, claiming the above "constant time" is calculated by ignoring the fact that we can have $n\to \infty$ since in practice $n$ does no go to $\infty$, if I understood the response. As for me, it is hard to believe this "constant time" is actually $O(2^n)$, constant time is really far from $O(2^n)$. I would be surprised to see such large approximations in a paper published by Real-Time Systems.

ps 2. Not really essential, but a technical edit: because of Step 5, the complexity of the algorithm should be $O(nm+m\cdot log(m))$ on a RAM-TM and not $O(nm)$, which is relevant only if $n$ is very very small compared to $m$.

Answer 1

Your algorithm involves an array of length $2^n$. Allocating an array of length $2^n$ takes $\Theta(2^n)$ time. Consequently, the running time will be $O(m+2^n)$.

Alternatively, you can represent the array in a sparse way using a self-balancing binary tree data structure. Then each access to the array takes $O(\log m)$ time, so the total running time of your algorithm is $O(m \log m)$ (assuming we can treat $n$ as a constant).

Alternatively, you could use a hash table to replace the array. Then the expected time per access is $O(1)$ if you use a suitable hash function, so your algorithm will have expected running time $O(m)$ (again, treating $n$ as a small constant). However, this is the expected running time, not the worst-case running time; the worst case could be as bad as $O(m^2)$.

You seem to have the idea that you can allocate and work with an array of exponential in constant time. I don't think that's correct. What is true is that you can simulate such an array, at the cost of a logarithmic increase in the running time (using the methods I described above). If you care only about whether the algorithm is polynomial-time or not, you can ignore the logarithmic increase, but if you care about the concrete running time, you can't ignore it.

And if you really care about the precise running time, you should probably specify the model of computation (e.g., transdichotomous model, etc.). For instance, in the transdichotomous model, if $n$ is guaranteed to be at most the word size (i.e., all of your integers fit within a word), then yes, your algorithm works and runs in linear time -- you can allocate/reserve memory for $2^n$ cells without difficulties. However if $n$ is larger than the word size, you can't. So, giving a precise answer to your question requires specifying a particular model of computation.

Related: Saving on array initialization.

Answer 2

I would argue that this is not an exponential algorithm on either Random Access Memory or a Turing Machine. On a Turing Machine you could compute as follows (assuming you have a symbol set and state set large enough to cover all of the integers. If not, you are going to have to do a more complex comparison, but that will only be a linear slowdown): Along the tape, alternate cells are the integers, and then counters next to them.

For each integer in the list:
    Iterate along the tape, and compare each cell with the current integer
    If it is the same, increment the relevant counter, otherwise move along the tape.
Once you have completed this for all of the integers, iterate along the tape again, and look for the highest counter. Output the integer next to the highest counter

This algorithm will take $4m$ steps per integer (two out and two back for each integer currently on the tape), multiplied by $m$ integers. It will then take $2m$ time to compare all of the counters, and $2m$ to return to the start to output the answer. This is a total of $4m^2+4m$, which is $O(n^2)$ By using RAM, either a hashtable or an exponential amount of memory can be used. For a hashtable, it is a worst case $O(n^2)$ algorithm, and best case $O(n)$, and with exponential memory it is $O(n)$.

Therefore, in answer to your question, no, it does not have to take exponential time on a Deterministic Turing Machine. Your implementation does, but only because you opted to use an exponential amount of memory. By using RAM, the algorithm can be reduced to $O(n)$ given sufficient memory, or $O(n^2)$ with reasonable limits.

Edited to answer both the comments and the edited question:

While the algorithm you use allocates an exponential amount of memory, as you correctly point out it does not write to it. Because of this, the TM can simulate the algorithm without needing the same number of memory locations. Where I have above written the integer to the tape, that is effectively a pointer to your exponential amount of memory. In the interests of simplicity I did not have my array in order, however had I inserted into the middle of the array, rather than appending new values. (at a cost of $O(n)$), then my algorithm would exactly simulate yours.

To demonstrate this difference, consider the following algorithm:

For an input of length n:
    write a 1 to the 2^nth cell
end

By your definition, this algorithm is exponential, because the TM would have to move out $2^n$ cells to write. When running this in RAM, it would take constant time. Crucially however, ONLY the $2^n$th cell has been written to, and the rest are undefined. For this reason, the TM could simulate it by writing a 1 to the first cell and ending. I would argue therefore, that this algorithm is constant time.

Based on the above logic, although your algorithm reserves an exponential amount of memory, it only ever uses a linear amount of it (the total amount required to transcribe the input). For this reason, it is not required for the TM to allocate an exponential amount of memory, it can also use a linear amount. This will take either $O(n^2)$ or $O(n^3)$ depending on whether or not you want the array in order.

In answer to your second point, yes, I sidestepped the issue of the amount of time taken to compare integers. I did this by assuming that the symbol and state set was large enough to accomodate the integers. If you ignore this assumption, there is a further $n^2$ slowdown. (I would note however that it's $n^2$ on the length of a single integer, not on the length of the input as a whole.)

In conclusion, depending on precisely how you simulate the algorithm, and what you define to be part of the machine vs variable with the input, the TM algorithm can range from $O(n^2)$ to $O(n^5)$, but is definitely polynomial.

Answer 3

So this is what I consider as the pitfalls of abstracting physical computation into a purely mathematical theory. First, to answer your question, by extended Church-Turing, when you implement your algorithm on a physical RAM machine, it will run in exponential time.

There are some subtle points here.

1. To access a uniformly random memory cell among all $2^n$ cells (of constant size, say, of bits), assuming general relativity and quantum mechanics, there is no way you can do this in $o(2^{n/3})$ time (proof left as exercise, hint: use concentration of volume).
2. There are no contradictions because when you reduce a RAM program with time $T$ and space $S$ into a Turing machine, the running time of the Turing machine will be ${\sf poly}(S, T)$. So extended Church-Turing thesis is robust as long as you don't use superpolynomial space. See also: Strongly polynomial time v.s. weakly polynomial time, although this particular example is not a typical example of weakly polynomial time.

To conclude, extended Church-Turing thesis really considers reasonable computational models, and the seeming contradiction really stems from the fact that you are making an unreasonable assumption that RAM access only costs constant time.

P.S. You can also consider similar "speed-ups" in the circuit model, in fact, you can prove that circuits can decide everything (including undecidable problems) in as much time as one needs to read the input.

Answer 4

Thanking everybody for the responses, I come myself with a solution that satisfies me at 99.99%, using arguments from your replies. The main idea is that the Turing Machine (TM) can simulate my RAM machine in polynomial time, provided an initialization axiom.

To be very clear, I can run my algorithm in $O(nm+m\log(m))$ time on a RAM-TM (Random Access Memory-Turing Machine). The RAM-TM is multi-tape TM with a memory and an index tape. Given a number written on the index tape, the RAM-TM takes constant time to jump the head of the memory tape to the location indicated on the index tape. We also allow the RAM-TM to have a few other tapes for easily doing arithmetics, and an input tape. We consider an additional program tape that represent instructions. For instance, scan, $+1$ could mean ''scan the input tape and for each number increment the memory content pointed by the number''. Incidentally, my algorithm also runs in polynomial time on a Transdichotomous RAM machine with word size $w=n+1$. I think D.W. agrees on this (last paragraph of the response).

A Turing Machine (TM) can simulate my RAM-TM in polynomial time, circumventing the fact that my RAM-TM has infinite memory, since the memory tape is infinite. Consider a whole execution of the RAM-TM consisting of running algorithms/programs $A_1$, $A_2$, $\dots$, $A_p$, where $A_p$ is my algorithm. If the total time complexity of all these runs is polynomial in $p$ and in the total input size of $A_1$, $A_2$, $\dots$, $A_p$, then the TM can simulate the whole execution in polynomial time.

We simulate the whole RAM-TM execution using a 2-tape TM, knowing that a 2-tape TM can be simulated in quadratic (hence polynomial) time by a TM. We use the second tape to store the accessed memory cells of the infinite RAM-TM memory. Since the RAM-TM execution is polynomial, the number of accessed cells is polynomial. We can simply use the second tape of the TM to store all accessed memory locations, each location together with its content. Whenever any of the algorithms accesses memory content $[x]$ on the RAM-TM, the 2-tape TM can scan the second tape in polynomial time and search for index $x$ and retrieve the associated content $[x]$.

I said I am satisfied at 99.9%, because I think we still need an initialization axiom. It is not clear what the 2-tape TM should do when it finds no content associated to some index $x$, i.e., if the RAM-TM asks to retrieve an uninitialized memory cell. We use the following axiom: when the RAM-TM is first turned on, the memory tape contains only zeros. This does not mean that my algorithm $A_p$ can rely on the fact that all uninitialized cells are 0. From the viewpoint of $A_p$, uninitialized cells have an undetermined value, due to the previous programs $A_1$, $A_2$, $\dots$, $A_{p-1}$.

Without this axiom, the RAM-TM can not be simulated as far as I can see. Imagine a RAM-TM that has the following memory state when first turned on: the infinitely many bits of the memory tape contain the binary digits of $\pi$. It can solve the following problem: given an integer $n$ as input, return the $n^\text{th}$ digit of $\pi$. It can do this by simply returning $[n]$ in $O(\log(n))$ time, where it needs $O(\log(n))$ to write $n$ on the index tape. If we try to simulate this using some multi-tape TM with $\pi$ on one of the tapes, it would need $O(n)$ time to go to the $n^\text{th}$ location on that tape. $O(n)$ is exponential compared to the input size $log(n)$.