In the definition of the complexity class NP, we allow the certificate to be polynomial in the input size. But do we ever need a certificate that is longer than the input?
In all the NP problems I could think of, we don't. The "worst" problem was factorization
, where the obvious incoding is $n+O(\lg(n))$ (where n is length of the number we wish factor; I just realized that the input also contain a maximal number, as the decision problem is: Do there exists a factor less than some number), because we want to tell where the first factor end and the second begins. However we don't need to tell this, the verifier could just try all possibilities. Furthermore, we could decide not to write the last bit of the factors, and this way we get a certificate that is shorter than the number we wish to factor. Do'h division is fast, so you could just give one of the factors as certificate.