A preliminary investigation of satisfiability problems not harder than 1-In-3-SAT

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in Buch/Sammelband/GutachtenBeigetragenBegutachtung

Beitragende

Abstract

The parameterized satisfiability problem over a set of Boolean relations Γ (SAT(Γ)) is the problem of determining whether a conjunctive formula over Γ has at least one model. Due to Schaefer's dichotomy theorem the computational complexity of SAT(Γ), modulo polynomial-time reductions, has been completely determined: SAT(Γ) is always either tractable or NP-complete. More recently, the problem of studying the relationship between the complexity of the NP-complete cases of SAT(Γ) with restricted notions of reductions has attracted attention. For example, Impagliazzo et al. studied the complexity of k-SAT and proved that the worst-case time complexity increases infinitely often for larger values of k, unless 3-SAT is solvable in subexponential time. In a similar line of research Jonsson et al. studied the complexity of SAT(Γ) with algebraic tools borrowed from clone theory and proved that there exists an NP-complete problem SAT(R≠ ≠ ≠01 1/3) such that there cannot exist any NP-complete SAT(Γ) problem with strictly lower worst-case time complexity: The easiest NP-complete SAT(Γ) problem. In this paper we are interested in classifying the NP-complete SAT(Γ) problems whose worst-case time complexity is lower than 1-in-3-SAT but higher than the easiest problem SAT(R≠ ≠ ≠01 1/3 ). Recently it was conjectured that there only exists three satisfiability problems of this form. We prove that this conjecture does not hold and that there is an infinite number of such SAT(Γ) problems. In the process we determine several algebraic properties of 1-in-3-SAT and related problems, which could be of independent interest for constructing exponential-time algorithms.

Details

OriginalspracheDeutsch
Titel41st International Symposium on Mathematical Foundations of Computer Science
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Seiten64:1-64:14
ISBN (Print)9783959770163
PublikationsstatusVeröffentlicht - 1 Aug. 2016
Peer-Review-StatusJa

Publikationsreihe

Reihe41st International Symposium on Mathematical Foundations of Computer Science (MFCS`16) ; Vol. 58
Band58
ISSN1868-8969

Externe IDs

Scopus 85012869811

Schlagworte

Schlagwörter

  • Clone Theory, Satisfiability Problems, Universal Algebra