# Why does not the definition of NP problems care about the complexity of guessing? [closed]

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, KavehMay 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
If this question can be reworded to fit the rules in the help center, please edit the question.

• This is not a research-level question, and as such it is off-topic on this site. It would be more appropriate for cs.stackexchange.com . – Emil Jeřábek May 5 '17 at 19:09

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