Satisfiability certificates verifiable in subexponential time

Evgeny Dantsin, Edward A. Hirsch

Research outputpeer-review

2 Citations (Scopus)

Abstract

It is common to classify 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 [IP01] on the dependence of the time complexity of k-SAT on k has its counterpart for the certificate complexity: we show that, assuming the exponential time hypothesis (ETH), the certificate complexity of k-SAT increases infinitely often as k grows. Another example of time-complexity results that can be translated into the certificate-complexity setting is the results of [CIP06] on the relationship between the complexity of k-SAT and the complexity of SAT restricted to formulas of constant clause density. We also consider the certificate complexity of CircuitSAT and observe that if CircuitSAT has subexponential-time verifiable certificates of length cn, where c < 1 is a constant and n is the number of inputs, then an unlikely collapse happens (in particular, ETH fails).

Original languageEnglish
Title of host publicationTheory and Application of Satisfiability Testing - 14th International Conference, SAT 2011, Proceedings
Pages19-32
Number of pages14
DOIs
Publication statusPublished - 27 Jun 2011
Event14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011 - Ann Arbor, MI
Duration: 19 Jun 201122 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6695 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011
CountryUnited States
CityAnn Arbor, MI
Period19/06/1122/06/11

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Satisfiability certificates verifiable in subexponential time'. Together they form a unique fingerprint.

  • Cite this

    Dantsin, E., & Hirsch, E. A. (2011). Satisfiability certificates verifiable in subexponential time. In Theory and Application of Satisfiability Testing - 14th International Conference, SAT 2011, Proceedings (pp. 19-32). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6695 LNCS). https://doi.org/10.1007/978-3-642-21581-0_4