License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.64
URN: urn:nbn:de:0030-drops-64769
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6476/
Go to the corresponding LIPIcs Volume Portal


Lagerkvist, Victor ; Roy, Biman

A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT

pdf-format:
LIPIcs-MFCS-2016-64.pdf (0.6 MB)


Abstract

The parameterized satisfiability problem over a set of Boolean relations Gamma (SAT(Gamma)) is the problem of determining whether a conjunctive formula over Gamma has at least one model. Due to Schaefer's dichotomy theorem the computational complexity of SAT(Gamma), modulo polynomial-time reductions, has been completely determined: SAT(Gamma) 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(Gamma) 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(Gamma) with algebraic tools borrowed from clone theory and proved that there exists an NP-complete problem SAT(R^{neq,neq,neq,01}_{1/3}) such that there cannot exist any NP-complete SAT(Gamma) problem with strictly lower worst-case time complexity: the easiest NP-complete SAT(Gamma) problem. In this paper we are interested in classifying the NP-complete SAT(Gamma) problems whose worst-case time complexity is lower than 1-in-3-SAT but higher than the easiest problem SAT(R^{neq,neq,neq,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(Gamma) 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.

BibTeX - Entry

@InProceedings{lagerkvist_et_al:LIPIcs:2016:6476,
  author =	{Victor Lagerkvist and Biman Roy},
  title =	{{A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6476},
  URN =		{urn:nbn:de:0030-drops-64769},
  doi =		{10.4230/LIPIcs.MFCS.2016.64},
  annote =	{Keywords: clone theory, universal algebra, satisfiability problems}
}

Keywords: clone theory, universal algebra, satisfiability problems
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI