12
$\begingroup$

I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS primality test, and I believe this works for COMPOSITE as well.

As for FACTOR,

$$FACTOR = \{(m,r) :\;\; \exists s \text{ such that} 1<s<r \text{ and } s \text{ divides } m\} $$

from what I have read it seems that it is in $NP \cap Co-NP$. I see that it is in $NP$ since a certificate would consist of a prime divisor of $m$ less than $r$. But what kind of certificate can establish that there is no such prime divisor (in polynomial time)?

$\endgroup$
  • 1
    $\begingroup$ For a language to be in NP proof that input belongs to the language has to have a certificate which can be verified in polynomial time. It does not mean that a certificate for inputs not belonging to the language exists which can be verified efficiently. $\endgroup$ – sashas Feb 5 '16 at 13:41
  • 2
    $\begingroup$ see also NP complete variant of factoring / Theoretical Computer Science $\endgroup$ – vzn Feb 5 '16 at 16:00
11
$\begingroup$

A certificate for there being no non-trivial divisor of $m$ smaller than $r$ is the factorization of $m$. We can check in polynomial time that all factors are indeed prime (since primality is in P by AKS primality test), that their product is $m$, and that all of them are at least $r$.

$\endgroup$
  • 1
    $\begingroup$ Thank you. And do I understand correctly that the AKS algorithm can tell us whether or not a number is prime in polynomial time, but if it is not prime it does not tell us the factors? $\endgroup$ – Fequish Feb 5 '16 at 14:51
  • 1
    $\begingroup$ @Fequish : ​ If it is not prime then AKS does not tell us the factors. ​ ​ ​ ​ $\endgroup$ – user12859 Feb 5 '16 at 15:38
  • 2
    $\begingroup$ Factoring isn't known to be doable in polynomial time. The best publicly known algorithm has heuristic complexity $e^{O((\log n)^{1/3}(\log\log n)^{2/3})}$ (here $n$ is the number itself). $\endgroup$ – Yuval Filmus Feb 5 '16 at 15:42
5
$\begingroup$

To add to Yuval's answer: AKS primality testing was discovered in 2002. Prior to that we didn't have a polynomial time algorithm to check if a number is prime. However Pratt discovered in 1975 what is now known as Pratt certificates for primality and proved that Primes is in NP. We can include these Pratt certificates of primality for the factors in our certificate to show that FACTOR is in coNP in place of using the AKS algorithm to check if factors are prime directly.

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