2
$\begingroup$

I have this question to solve. According to my understanding, it basically requires a turing machine that outputs lines on the tape, with the number of the lines being any prime number.

My idea is to take the AKS test's conclusion and making a case that since, calculating primes is a problem that can be solved in polynomial time complexity as already proven by AKS, hence this problem is also in P.

Is this the right way? what would be a more formal/mathematical way of expressing this if it is?

$\endgroup$
4
$\begingroup$

You can use the following algorithm:

  • Input: number $n$ encoded in unary
  • For $k$ from $2$ to $n-1$, check whether $k \mid n$, and if so, output "Not prime".
  • Output "Prime".

This algorithm runs in time polynomial in $n$.

The AKS test, in contrast, runs in time polynomial in $\log n$, assuming that the input $n$ is encoded in binary. If the input is encoded in unary, the running time (at least on a multitape Turing machine) will be $O(n)$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. There are a couple of things i don't understand though. Why do you count to n - 1? and what does $k∣n$ mean? $\endgroup$ – Blitz Mee Jan 18 at 23:01
  • 1
    $\begingroup$ The notation “$k \mid n$” means “$k$ divides $n$”. I’ll let you figure out the rest. $\endgroup$ – Yuval Filmus Jan 18 at 23:06
4
$\begingroup$

Hint: Notice that your input is unary.

$\endgroup$
  • $\begingroup$ if im not mistaken, your point is that since all unary numbers can be recognized by a turing machine in polynomial time, and all prime unaries are subset of all unary numbers, the complexity of the latter is also in P? $\endgroup$ – Blitz Mee Jan 18 at 20:20
  • 1
    $\begingroup$ @Blitz Nope, that is not true in general. For example, there are undecidable unary languages. The point is that the unary representation of a number is exponentially larger than a base-$k$ representation of the same number for $k \geq 2$. Consider the impact of this on your time complexity. $\endgroup$ – Aaron Rotenberg Jan 19 at 1:08
-1
$\begingroup$

Also, Another point is that if we use anything except unary base, the problem is NP. for example for binary mode, the length of our number is log(n) and we have (n - 1) numbers before it. So it needs exponential time to decide whether is prime or not.

$\endgroup$

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.