# NP-problem that needs superlinear certificates

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.

• If you could prove that some problem in NP requires superlinear certificates, you'd have proved P≠NP, because you'd have ruled out the existence of a program that needs no certificate at all. (Of course, the same is true for any nonconstant/nonzero function in place of superlinear.) Jun 16, 2011 at 6:15

Graph isomorphism is an example of a "natural" problem where the obvious certificate is superlinear. It is $n \log n$.
You can artificially create an NP problem which seems to require longer certificates: given an instance $x$, answer some predicate on $G(x)$, where $G$ is some PRNG that takes an input of size $n$ and outputs a string of size $n^2$. Now the certificate would be quadratic (though probably no-one knows whether it has to be that large).
• I know that no one can prove that the certificate must be super linear: If we could prove that we need a certificate, we would have a proof that $P\neq NP$. Dec 22, 2010 at 16:07
• It seems like we could use diagonalization to get a hierarchy on certificate sizes. I haven't really that it through, but that seems doable. [Assuming that $P\not=NP$, of course.] Dec 22, 2010 at 22:43