I have a question regarding the definition of NP problems. According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time. However, this definition does not account for two things. First, how many certificates the problem can have? Should it be harder to deal with problems which have infinitely many certificates (even thought still in polynomial sizes) than ones that have only few? Why does not this feature affect the complexity of the underlying problem? Second, why does the size of the certificate (witness) but not the complexity of the guessing take a role in this definition? I would really appreciate any clarification of this confusion.
closed as off-topic by Emil Jeřábek, Joshua Grochow, cody, Jukka Suomela, Kaveh May 5 '17 at 21:28
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Joshua Grochow, cody, Jukka Suomela, Kaveh
According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time.
No, there is nothing about guessing in the actual definition. It is required that a certificate exist if the answer is "yes" (and doesn't exist if the answer is "no") and that verification of a proposed certificate takes polynomial time. The definition specifically doesn't require that there is any way to obtain the certificate if one exists, so we sometimes talk about "guessing" it. But it could equally be replaced e.g. by "if an alien gives you a string and claims it's a certificate for an instance, you can verify this in polynomial time". In any case, neither "guessing" nor "being given by an alien" have any complexity we could talk about.
In fact, for any $NP$ problem there are algorithms allowing to find a certificate for any instance (if one exists, i.e. if the answer is positive). But if this algorithm is polynomial, then the problem is actually in $P$, and for $NP$-complete problems only exponential algorithms are known.
which have infinitely many certificates (even thought still in polynomial sizes) than ones that have only few
For any $n$ and for any polynomial of $n$ there is a finite number of strings of that length. Even if all of them are certificates (such as in the proof that $P$ is a subset of $NP$), you can't have an infinite number of certificates.