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

>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?

.

Relevant Pages