<blockquote>
  <p>According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time.</p>
</blockquote>

<p>No, there is nothing about guessing in the actual definition. It is required that a certificate <em>exist</em> if the answer is "yes" (and doesn't exist if the answer is "no") and that <em>verification</em> 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.</p>

<p>In fact, for any $NP$ problem there <em>are</em> 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.</p>

<blockquote>
  <p>which have infinitely many certificates (even thought still in polynomial sizes) than ones that have only few</p>
</blockquote>

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

CC BY-SA 3.0
2017-05-05T18:47:37.607Z
2017-05-05T19:00:15.960Z
2017-05-05T19:00:15.960Z
Alexey Romanov
<p>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.</p>

CC BY-SA 3.0
2017-05-05T19:09:21.057Z
This is not a research-level question, and as such it is off-topic on this site. It would be more appropriate for https://cs.stackexchange.com .
Emil Jeřábek
<np><complexity>
Why does not the definition of NP problems care about the complexity of guessing?
Nguyen
# Why does not the definition of NP problems care about the complexity of guessing?

(Asked by: username_0 on 2017-05-05)

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.

**Tags:** np, complexity

> **Comments:**
> **username_1**: This is not a research-level question, and as such it is off-topic on this site. It would be more appropriate for https://cs.stackexchange.com .  

---

## 1 answers

### Answer by username_2 on 2017-05-05. Score: 3

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


---

