Re: Can someone give me an example of this type of problem?

>Primality is in NP (it is now known to be in P). The certificate was a short
>proof of primality. A similar certificate could exist for the problem
>being discussed. A proof that an (x,y,z) exist need not actually
>identify (x,y,z), just as an algorithm that decides if a number
>is prime or composite need not actually identify any factors.

In the case of primality, the certificate is a solution to the
problem, "Are there numbers that satisfy a specific relation?"
The "primality relation" bounds the solution to numbers less than
the given prime.

Are all witnesses the solution to a similar type of relation? It
would appear so.

.

Relevant Pages