2
$\begingroup$

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
    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.)2011-06-16

2 Answers 2