0
$\begingroup$

Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th prime number (written in binary)? And writing the first $n$ primes followed by their product (all written in binary)?

$\endgroup$
3
  • $\begingroup$ Homework? What did you try? $\endgroup$
    – Pål GD
    Jan 30, 2013 at 20:43
  • $\begingroup$ What does $1^{n \times n}$ mean; $n^2$ many ones? $\endgroup$
    – Raphael
    Jan 30, 2013 at 20:59
  • $\begingroup$ Yes. I only know that in order to find n primes I must check at least n*log(n) numbers. So for every x in 2..n I can mark every non prime number x^i using the Sieve of Eratosthenes up to n^2 O(n^2*log(n)*log(log(n))). Whenever I find one I can write it on the output tape O(log(n)) $\endgroup$
    – user6638
    Jan 30, 2013 at 21:29

1 Answer 1

2
$\begingroup$

Since the input is of length $n^2$, it makes sense that the TM must read it at least once (to learn the value of $n$), and we have a trivial lower bound of $\Omega(n^2)$. It is my understanding that what you actually ask is "can we complete the task with $O(n^2)$ steps as well"?

You suggest using the Sieve of Eratosthenes to mark primes. This is a clever idea. Indeed, a possible TM can run over the input. Each time it finds a 1, it writes its index on the output tape ($p_i$), and go through the input tape, zeroing any multiply of $p_i$. Then it goes back to index $p_i$ and repeat.

In order to know the index, we can assume the TM maintains a counter on the output tape (which is being "pushed" every time the TM outputs a new prime).

Now let's analyze the running time.

  1. reading the input - $n^2$
  2. For any prime we find (and we have $n$ of those:)
    1. mark the input tape according to the Sieve of Eratosthenes: we need to go through approximately $O(n\log n)$ numbers due to the density of primes - $O(n\log n)$
    2. push the index and write the output - $O(\log n)$
    3. counting exactly $p^i$ steps between two indexes we zero - $O(n\log^2n)$
  3. Multiplying all primes - $O(n^2\log^{1+\epsilon}n)$

so the naïve solution above takes $O(n^2) + n\times [ O(n\log n) + O(n\log^2 n)] + O(n^2\log^{1+\epsilon} n)= O(n^2\log^2n)$. In the above I assumed counting takes $O(n\log^2 n)$ since each step we need to subtract 1 from a $\log n$-long number, for every step in the sieve (which we bound to length $O(n\log n)$).

The time complexity of that algorithms is $O(n^2\log^2 n)$.

However, things can get better, as there are other ways of sieving. Assuming a multitape TM, the sieve of up to $k$ can be computed using $O(k/\log\log k)$ additions (thus, with $O(k\log k/\log\log k)$ bit-operations) by [1]. By setting $k=O(n\log n)$, we can compute the sieve with $O(n\log n)$ steps.

However, computing the multiplication of $n$ numbers (of length $\log n$) will take $n \times O(MUL_{\log n})$ where $MUL_k$ is the time to multiply two numbers of length $k$. According wikipedia, $MUL_k \approx O(n\log n )$ [2]. This step alone is $\Omega(n^2\log n)$ and I don't see much hope to get complexity of $O(n^2)$.


[1]: A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms" (free-access), Mathematics of Computation 73 (2004), pp. 1023–1030.
[2]: ignoring the practically constant term of $2^{\log^* n}$.

$\endgroup$

Your Answer

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

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