0
$\begingroup$

Bear in mind I'm almost a complete noob at complexity theory.

I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, does that imply finding all prime numbers less than a number n is also doable in polynomial time and thus the algorithm runs in FP. Additionally, does this imply that counting all primes less than n is not in #P?

Any ideas, or comments are appreciated Thanks!

$\endgroup$
  • 3
    $\begingroup$ The number of primes in $\{1, \ldots, n\}$ is $\theta(\frac{x}{\log x})$, which is more than polynomial in the length of $n$. Simply listing the primes would take too long. $\endgroup$ – Solomonoff's Secret Jun 24 '18 at 2:24
  • $\begingroup$ You can list the primes less than $n$ in $O(n^k)$ (for some $k$), but not in $O(\log^k n)$. Usually, in number theory, it's the latter which is called "polynomial time", not the former, since $n$ is exponential in the number of digits. $\endgroup$ – chi Jun 24 '18 at 9:17
4
$\begingroup$

No, it doesn't. There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.

$\endgroup$
1
$\begingroup$

The answer by D.W. already points out that listing all primes up to $n$ cannot be done in time polynomial in the representation of $n$.

It can be done in time polynomial in $n$, though. Using the sieve of Eratosthenes, the running time is $n\log n$.

You had one other question: Whether counting primes can be done in #P. Yes, it can. This is a direct consequence of having a PTIME primality test. (And it would not have been contradicted by (listing or) counting being in FP, as FP is a subclass of #P.)

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