1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 . $\endgroup$ – Emil Jeřábek May 5 '17 at 19:09
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.