Problem Detail: 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)?
Asked By : Fequish
Answered By : Yuval Filmus
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52722 Ask a Question Download Related Notes/Documents
