It is common to classify Boolean satisfiability problems by their time complexity. We consider another complexity measure, namely the length of certificates (witnesses). Our results show that there is a similarity between these two types of complexity if we deal with certificates verifiable in subexponential time. In particular, the well-known result by Impagliazzo and Paturi on the dependence of the time complexity of k-SAT on k has its counterpart for the certificate complexity: we prove that, assuming the exponential time hypothesis (ETH), the certificate complexity of k-SAT increases infinitely often as k grows. We also consider the certificate complexity of CIRCUIT-SAT and show that if CIRCUIT-SAT has subexponential-time verifiable certificates of length cn, where c is a constant strictly less than 1, and n is the number of inputs, then an unlikely collapse of complexity classes occurs (which in particular implies that ETH fails).

Joint work with Edward A. Hirsch.