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.

  • 2
    $\begingroup$ 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.) $\endgroup$ – ShreevatsaR Jun 16 '11 at 6:15

Graph isomorphism is an example of a "natural" problem where the obvious certificate is superlinear. It is $ n \log n$.


In the definition of NP, no attempt is made to shorten the size of the certificate. Since the running time is polynomial and the machine might "guess" at each step, the certificate is polynomial.

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).

As an aside, "factorization" is not an NP predicate. To make it a predicate, you need to ask some "hard-core" question on one of the factors.

  • $\begingroup$ 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$. $\endgroup$ – Sune Jakobsen Dec 22 '10 at 16:07
  • $\begingroup$ But, thanks for the answer. I would still be interested to hear if there exist some less artificial NP problem. $\endgroup$ – Sune Jakobsen Dec 22 '10 at 16:09
  • $\begingroup$ 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.] $\endgroup$ – Jeremy Hurwitz Dec 22 '10 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.