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

jeffrey_h_miller@xxxxxxxxx wrote:
>>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.

The certificate was a proof that the number was prime.
It was a proof that there did not exist any non trivial
factors. I do not know what you mean by 'the "primality relation"
bounds the solution to numbers less than the given prime.' You
cannot list all the possible non-factors of a prime number
in polynomial time.

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

I am not sure what you are trying to say. There is a big
difference between the certificate for a problem like primality than
for a problem like composites. In the latter case, the
certificate is a non-trivial factor. This is the
case for many problems in NP, that the solution to the
non-decision version of the problem is the certificate.
However for some problems the certificate is something else,
and just because you cannot think of such a certificate
does not mean the problem is not in NP.

Stephen
.

Relevant Pages