Computer Science Asked by builderthebob00 on February 6, 2021
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!
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:
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$).
Answered by Steven on February 6, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP