For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I can think of two ways for this to happen:
- It isn't obvious that the problem is in NP. The only example I can think of is the language of primes which requires (before AKS) primality certificates which are not obvious. However, I'm hoping for languages which are hard (not in BPP) without a certificate.
- A certificate can be shorter than the natural certificate. This is the case for many FPT problems, since you can provide a certificate for the kernel. What other languages are there with this property?