0
$\begingroup$

Question:

Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?

I know that for every composite number, a factor of the number is a certificate. Verification proceeds by dividing the number by the factor and checking if the reminder is zero. My question is whether the verification can be done in polynomial time of $n$? it seems that we need to use at most $2^n/2 = 2^{n-1}$ factors to test, does that mean we should use exponential time to verify?

$\endgroup$
1
$\begingroup$

NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.

So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So “is x composite” is quite obviously in NP.

The opposite, “is x a prime”, has been shown to be in NP, but that is absolutely not easy to show. Basically you have to show that for any n-bit prime p, there is a certificate that allows us to verify in polynomial time time that p is prime.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

It's almost always the case that problem sizes are expressed as a function of the length of the input, so a number n would be taken to be $\log n$ in length. For example, your verification would be in poly time if it ran in $O(\log^k n)$ time for some integer $k$.

| cite | improve this answer | |
$\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.