3
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ You claim that there is no polynomial time algorithm for a TM machine solving that problem, or you say there is no LINEAR time algorithm for that problem? Time complexity may change depending on what model you choose. But I think your problem is solvable in polynomial time on a deterministic TM. $\endgroup$
    – fade2black
    Jul 20, 2017 at 21:28
  • $\begingroup$ Thanks for this reply. I do not really claim there is no Linear algorithm, not essential (by the way, I think the TM needs $O(n^2)$ to compare two numbers on n digits). I agree the deterministic TM can solve it in polynomial time. But the algorithm itself, is it really polynomial on a RAM machine? If yes, how could a TM simulate it with only a polynomial time overhead as stated by the citation from [55]? There are some extended Church-Turing theses claiming the TM can simulate any realistic computation model up to polynomial-time reductions (sec "Variations" in the Church-Turing wiki article). $\endgroup$ Jul 20, 2017 at 21:42
  • 1
    $\begingroup$ You say that "[...] Turing machine should be able to simulate my algorithm in polynomial time" but at the same time you demand that you should be able to create a $2^k$ size "array" in the RAM model, whereas this must take $2^k$ time in a Turing Machine model. Well, then, of course the TM will be exponentially slower than the RAM machine, but only because you demand it. $\endgroup$
    – Pål GD
    Jul 21, 2017 at 18:11
  • $\begingroup$ Two more things. You need to reserve $2^{n \log m}$ cells to hold your information, second, in your question regarding binary search, you are given the "array" an an input to the algorithm, i.e., the array is already allocated and populated. Nobody claims you're able to construct and populate an array of $n$ elements in $\log n$ time. $\endgroup$
    – Pål GD
    Jul 22, 2017 at 8:06
  • $\begingroup$ @Pål GD, thanks for your replies, I agree. If you think I need to edit my question to take these remarks into account, please specify the information I need to update. I said we need $2^n$ cells, each one large enough to store $m$, which is perfectly equivalent to using $2^{n~\text{log}(m)}$ bits as you said (incidentally, you actually said "$2^{n~\text{log}(m)}$ cells", but I assume you thought about bits). $\endgroup$ Jul 22, 2017 at 11:24

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Could you please expand on why allocating $O(2^n)$ bits requires $O(2^n)$ time? I do not fully agree on this. You think this holds on which RAM machine(s)? Regarding the real-life machines, there is at least a memory allocator that "performs the allocation/deallocation in constant time maintaining a very low memory fragmentation.", citing page 150 of [M. Masmano, I. Ripoll, P. Balbastre, and A. Crespo. A constant-time dynamic storage allocator for real-time systems. Real-Time Systems, 40(2):149-179, 2008]. My algorithm should be polynomial when using with this allocator, no? $\endgroup$ Jul 21, 2017 at 9:24
  • $\begingroup$ @DanielPorumbel, I haven't read that paper, but my guess would be that it is constant-time in a particular model. Ultimately, memory allocators tend to rely on virtual memory, which tend to rely on a page table datastructure, which are based on a tree data structure, and in the end, as $n \to \infty$, the cost of accessing a page you've never accessed before is $O(\log n)$. (We treat it as $O(1)$ in real machines because in real life $n$ doesn't get very large, but if you want to do asymptotic analysis, arguably it really should be considered $O(\log n)$ time.) $\endgroup$
    – D.W.
    Jul 21, 2017 at 16:44
  • $\begingroup$ So if you're using virtual memory to support memory allocation of extremely large memory regions, of which you write to only a small amount of... you're basically using the "simulate the array using a tree data structure" without realizing it. The hardware is doing the tree for you, so it's not visible to you, but it's there. Anyway, if we want to make really precise statements about running time, we have to fix a specific model of computation, and that requires deeper analysis than what's in my answer. $\endgroup$
    – D.W.
    Jul 21, 2017 at 16:45
  • $\begingroup$ @ D.W. If you don't trust the memory allocator is really constant-time as claimed (by the way, you seem to accept a complexity of $O(log n)$ which is not $O(2^n)$ and would keep my algo polynomial), please check my first argument below point 1 on the edited question. I can simply consider a RAM machine only for my algorithm. My algorithm would not need memory allocation on this machine, because it can have the whole available memory at its disposal. It can simply put aside the first $O(2^n)$ bits and access them in constant time using the formalization of the RAM machine. $\endgroup$ Jul 21, 2017 at 16:57
  • $\begingroup$ @DanielPorumbel, it's simple since changing $f(n)$ bits requires $\Omega(f(n))$ time. Because changing a bit in $0$ time is impossible. We consider that machine memory is not essentially bounded by constant unlike computer. $\endgroup$
    – rus9384
    Jul 21, 2017 at 20:50
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks, I agree to what you said. But you actually only prove that the Turing machine solves the problem in polynomial time, using a different algorithm. But the extended Church-Turing theses mentioned at the end of my question seem to say that the Turing machine can simulate RAM machines with polynomial overhead. This would mean that the Turing machine should be able to simulate my algorithm in polynomial time. I don't know how this could happen? $\endgroup$ Jul 21, 2017 at 9:30
  • $\begingroup$ A second comment, less important. In the complexity of you Turing Machine (TM) algorithm, do you think the TM can compare two integers on $n$ bits in less than $O(n^2)$? Did you take this into account in the TM complexity calculation? I think this is one of the reasons why multi-tape TMs are useful: they can recognize language $xx$ in linear time, while the TM needs $n^2$ moves, where $n$ is the binary size of $x$. $\endgroup$ Jul 21, 2017 at 9:40
  • $\begingroup$ @DanielPorumbel, "simulate the algorithm" doesn't mean it works exactly identically. The simulation might do all sorts of clever things... including replacing a giant array with a small sorted list, as this answer suggests. $\endgroup$
    – D.W.
    Jul 22, 2017 at 1:40
  • $\begingroup$ @C Baish, thanks for the response. As far as I can see, you still use an additional assumption that the input comes alternating the integers and the counters. It is simple to avoid this by using a second tape for the counters. A TM with two tapes can be simulated in quadratic time by a TM with one tape. The second tape could well represent the contents of my utilized memory cells. Less importantly, your $m$ and $n$ notations are a bit confusing, because your $n$ is not my $n$ but it is the input size which is also $m$, assuming "my $n$" (size of each integer) is a bounded constant (?). $\endgroup$ Jul 22, 2017 at 10:42
  • $\begingroup$ @C Baish,@D.W. maybe you both found the key: simulate the huge memory with a polynomial size list. This list can work somehow as a virtual memory with polynomial access time. It is enough to use a lame list, no need for a faster red black tree. I will try to answer the question myself by adapting this ideas to bring the resulting Turing machine closer to what I understand by "simulation". As it stands the algorithm of C. Baish is not (yet) a simulation for my taste, because it requires a particular input structure. This can however be easily avoided with a second tape as in my above comment. $\endgroup$ Jul 22, 2017 at 10:52
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Welcome to CS.SE! $\endgroup$
    – D.W.
    Apr 3, 2020 at 22:48
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.