0
$\begingroup$

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.

Show the following language is in NP:

Not-Prime = {n ∈ N: n is not a prime number}

So far, I have created an efficient decider for the language with a certificate, but I'm not sure how to prove that the language is actually in NP. Thank you for any advice!

$\endgroup$
0
2
$\begingroup$

If you created a deterministic polynomial-time algorithm $A$ that can check a "yes"-certificate for Not-Prime (of polynomial length in the size of instance), then you already proved that your problem is in $\mathsf{NP}$.

Say that a polynomial upper bound on the length of the certificate is $p(s)$, where $s$ is the size of the instance. A non-deterministic polynomial-time algorithm for Not-Prime can do the following:

  • Guess the length $\ell$ of the certificate in $\{0, \dots, p(s)\}$.
  • For $i=1, \dots, \ell$: guess the $i$-th bit $c_i$ of the certificate.
  • Run $A$ on the certificate $c_1 c_2 \dots c_\ell$. If $A$ accepts, accept. Otherwise reject.

A certificate for an instance $n$ of Not-Prime is just a non-trivial prime factor of $n$ (which requires at most $\lceil \log n \rceil$ bits to be represented, so you can pick $p(s)=s$).

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