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 polynomialtime reductions, has
been completely determined: SAT(Gamma) is always either tractable
or NPcomplete. More recently, the problem of studying the
relationship between the complexity of the NPcomplete cases of
SAT(Gamma) with restricted notions of reductions has attracted
attention. For example, Impagliazzo et al. studied the complexity of
kSAT and proved that the worstcase time complexity increases
infinitely often for larger values of k, unless 3SAT 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 NPcomplete problem
SAT(R^{neq,neq,neq,01}_{1/3}) such that there cannot exist any NPcomplete SAT(Gamma) problem with strictly lower worstcase time complexity: the easiest NPcomplete SAT(Gamma) problem. In this paper
we are interested in classifying the NPcomplete SAT(Gamma)
problems whose worstcase time complexity is lower than 1in3SAT 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 1in3SAT and related problems, which could be of independent interest for constructing exponentialtime 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 1in3SAT}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {64:164:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6476},
URN = {urn:nbn:de:0030drops64769},
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 