Seminar: May 3

Evgeny Dantsin, Roosevelt University

On the Certificate Complexity of Boolean Satisfiability

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.