The Time Complexity of Constraint Satisfaction

Abstract

We study the time complexity of (d,k)-CSP, the problem of deciding satisfiability of a constraint system Open image in new window with n variables, domain size d, and at most k variables per constraint. We are interested in the question how the domain size d influences the complexity of deciding satisfiability. We show, assuming the Exponential Time Hypothesis, that two special cases, namely (d,2)-CSP with bounded variable frequency and d-UNIQUE-CSP, already require exponential time Ω(d ^c·n ) for some c > 0 independent of d. UNIQUE-CSP is the special case for which it is guaranteed that every input constraint system has at most 1 satisfying assignment.