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

jeffrey_h_miller@xxxxxxxxx wrote:
>>First of all, I think he meant to say "the witness (x, y, z)" rather than
>>"the witness (u, v, w)." The issue is not that the size of the instances
>>can get arbitrarily large, but that the size of the witness is arbitrarily
>>large.

> Yes, thanks for the correction.

> ...

>>However, all this shows is that this method of trying to prove that the
>>problem is in NP fails. It does not prove that the problem is not in NP.
>>There might be some other very complicated but short certificate that
>>works.

> Can you expound on a certficate that isn't a solution? Would "YES"
> from an algorithm that is proven to solve the problem be considered
> a short witness? What exactly is an acceptable witness?

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.

Stephen


.