Jonsson, Peter ;
Lagerkvist, Victor ;
Roy, Biman
Time Complexity of Constraint Satisfaction via Universal Algebra
Abstract
The exponentialtime hypothesis (ETH) states that 3SAT is not solvable in subexponential time, i.e. not solvable in O(c^n) time for arbitrary c > 1, where n denotes the number of variables. Problems like kSAT can be viewed as special cases of the constraint satisfaction problem (CSP), which is the problem of determining whether a set of constraints is satisfiable. In this paper we study the worstcase time complexity of NPcomplete CSPs. Our main interest is in the CSP problem parameterized by a constraint language Gamma (CSP(Gamma)), and how the choice of Gamma affects the time complexity. It is believed that CSP(Gamma) is either tractable or NPcomplete, and the algebraic CSP dichotomy conjecture gives a sharp delineation of these two classes based on algebraic properties of constraint languages. Under this conjecture and the ETH, we first rule out the existence of subexponential algorithms for finite domain NPcomplete CSP(Gamma) problems. This result also extends to certain infinitedomain CSPs and structurally restricted CSP(Gamma) problems. We then begin a study of the complexity of NPcomplete CSPs where one is allowed to arbitrarily restrict the values of individual variables, which is a very wellstudied subclass of CSPs. For such CSPs with finite domain D, we identify a relation SD such that (1) CSP({SD}) is NPcomplete and (2) if CSP(Gamma) over D is NPcomplete and solvable in O(c^n) time, then CSP({SD}) is solvable in O(c^n) time, too. Hence, the time complexity of CSP({SD}) is a lower bound for all CSPs of this particular kind. We also prove that the complexity of CSP({SD}) is decreasing when D increases, unless the ETH is false. This implies, for instance, that for every c>1 there exists a finitedomain Gamma such that CSP(Gamma) is NP complete and solvable in O(c^n) time.
BibTeX  Entry
@InProceedings{jonsson_et_al:LIPIcs:2017:8071,
author = {Peter Jonsson and Victor Lagerkvist and Biman Roy},
title = {{Time Complexity of Constraint Satisfaction via Universal Algebra}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {17:117:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8071},
URN = {urn:nbn:de:0030drops80710},
doi = {10.4230/LIPIcs.MFCS.2017.17},
annote = {Keywords: Clone Theory, Universal Algebra, Constraint Satisfaction Problems}
}
01.12.2017
Keywords: 

Clone Theory, Universal Algebra, Constraint Satisfaction Problems 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

01.12.2017 