1
$\begingroup$

In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/constant, $O(1)$, sum of $2$ small numbers requires $O(1)$ actions and their size is $O(1)$ bits for representation.

I'd like to analyse an efficient algorithm for this. The algorithm sorts $A$ and then iterates over the endpoints. If their sum is less than $\alpha$, we will check the second smallest element and the largest. If their sum is larger, we will check the smallest and the second largest. So on and on.

This algorithm takes $O(n\log n)$ due to sorting. However, trying to write it as a single-work tape TM, I'm having trouble. Assuming we have $2$ tapes: one read only tape for the input, and another read/write for the working process.

Sorting the array and writing it on the TM takes $O(n\log n) $ by merge sort, using a single tape. However, what about the process itself of comparison?

If we had $2$ tapes, or a single tape with $2$ access heads, we could have done trivially in $O(n)$. But having a single tape seems to be problematic, as I might run back and forth many times, and running back and forth might take $O(n)$.

My question follows: is there a way to implement this algorithm, or any other algorithm for pair-sum, such that it will need $O(n\cdot \log n)$ runtime, on a TM with $2$ tapes: the first is read only and the second is read-write?

$\endgroup$
9
  • $\begingroup$ "their size is $O(1)$ bits for representation.". That implies all numbers in $A$ are smaller than a constant $c$. This implies there is a simple $O(n)$ algorithm using one read-only one tape. $\endgroup$
    – John L.
    Jun 1 at 18:05
  • $\begingroup$ In fact, with reasonable assumption on the representation of $\alpha$, there is a definitive finite automaton that solves the problem. $\endgroup$
    – John L.
    Jun 1 at 18:36
  • 1
    $\begingroup$ Assuming each value comes from a constant range, say $[0,...,c-1]$, we can perform a sort of a count sort. We know the value range ahead of time, and we declare the bits $i\cdot \log n , ...., (i+1) \cdot \log n -1$ to be used by the value $i$. It will represent a counter that indicates how many of $A$'s cells have the value $i$, and therefore it needs $\log n$ bits. Now, we iterate over the read-only tape. Whenever we see a certain value, we go to the corresponding $i$'s cells and $\endgroup$ Jun 2 at 17:42
  • 1
    $\begingroup$ then increase the number there by $1$. Going to that cell requires at most $c \cdot \log n$ moves which is within $O(\log n)$. Increasing the value is also $O(\log n )$. This is performed for each value in $A$. Therefore, $O(n \cdot \log n)$. $\endgroup$ Jun 2 at 17:42
  • 1
    $\begingroup$ Is $c$ fixed, that is can I assume that this value is built into the TM? $\endgroup$
    – Russel
    Jun 6 at 14:01

1 Answer 1

3
+50
$\begingroup$

Summary: There is no need to sort the given numbers since whether there are two numbers in $A$ such that their sum is $\alpha$ depends on the set of numbers in $A$. Since the choices for the set of numbers in $A$ is $O(1)$, there is an $O(n)$-time algorithm/TM with one read-only tape.


Assume that multiset $A$ and a number $\alpha$ are given as $c_{a_i}\square c_{a_2}\square\cdots\square c_{a_m}\square' c_{\alpha}$ as input on the tape, where

  • $c_{a_i}$ stands for the cells that represent $a_i$, the $i$-th number in $A$ as a binary number.
  • $c_{\alpha}$ stands for the cells that represent $\alpha$ as a binary number.
  • $\square$ and $\square'$ are two field separators (neither of them appear in $c_*$).

Since "their size is $O(1)$ bits for representation", there is a constant $c\in \mathbb N$ such that each number in $A$ uses at most $c$ cells, i.e., $a_i\in [2^c] = \{0,...,2^c−1\}$.

Let us specify Turing machine (TM) $M$ as follows.

Given the input as described above, TM $M$ will,
    for each number $x\in[2^c]$:
        check whether $x$ is in $A$. If yes, for each number $y\in \{x+1, x+2, \cdots, 2^c-1\}$:
            check whether $y$ is in $A$. If yes, check whether $x+y=\alpha$. If still yes, halt and accept.
    for each number $x\in[2^c]$:
        check whether $x$ appears in $A$ at least twice. If yes, check whether $2x=\alpha$. If still yes, halt and accept.
    Halt and reject.

Since $c$ is a constant, we can hardcode all "for" loops, $x$, $y$, the result of each check, $x+y$, $2x$, etc. using states and state transitions of $M$. There is no need to alter any tape cell.

Each "check" above involves moving the head of $M$ from the start of the input to the end of the input, and then back to the start of the input, which takes $O(n)$ time. The total running time of $M$ is no more than $2^c2^c2O(n) + 2\cdot2^cO(n)$, which is $O(n)$ still.

We can improve the algorithm/$M$ so that it could run faster with less states. However, that is another task.

$\endgroup$
2
  • $\begingroup$ That's a nice way to approach this! It reminds me a bit of count-sort. If we would know that all the values are from a range $1,...,m$, where $m$ is no longer a constant, we would then need to attempt a sorting-like approach? $\endgroup$ Jun 9 at 6:45
  • $\begingroup$ I am not sure what might be the fastest approach. $\endgroup$
    – John L.
    Jun 9 at 18:51

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.