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

....
>Yes, you can probably make some kind of intuitive
>argument that even a primality certificate is a "solution"
....
>though I suppose you can still think of
>it intuitively as an error-correcting coding of a solution
....

Yes, I suppose that all such witnesses are solutions.
Thanks for pointing out that they *MUST* be and that
strings that just say things like "YES" or "NO" can't
generally be witnesses as they aren't generally "solutions"
to any but the simplest relationships.

.

Relevant Pages