research-article

Fine-Grained Time Complexity of Constraint Satisfaction Problems

Authors:

Victor Lagerkvist,

Biman RoyAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 13, Issue 1

Article No.: 2, Pages 1 - 32

https://doi.org/10.1145/3434387

Published: 21 January 2021 Publication History

Abstract

We study the constraint satisfaction problem (CSP) parameterized by a constraint language Γ (CSPΓ) and how the choice of Γ affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSPΓ problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain D and where all unary relations are available, we identify a relation S_D such that the time complexity of the NP-complete problem CSP({S_D}) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({S_D}) strictly decreases when |D| increases (unless the ETH is false) and provide stronger complexity results in the special case when |D|=3.

References

[1]

V. B. Alekseev and A. A. Voronenko. 1994. On some closed classes in partial two-valued logic. Discrete Mathematics and Applications 4, 5 (1994), 401--419

[2]

L. Barto. 2014. The constraint satisfaction problem and universal algebra. ACM SIGLOG News 1, 2 (Oct. 2014), 14--24.

Digital Library

[3]

L. Barto and M. Pinsker. 2016. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16). ACM, New York, NY, 615--622.

[4]

M. Behrisch, M. Hermann, S. Mengel, and G. Salzer. 2019. Minimal distance of propositional models. Theory of Computing Systems 63, 6 (Aug. 2019), 1131--1184.

Digital Library

[5]

M. Bodirsky. 2012. Complexity classification in infinite-domain constraint satisfaction. Mémoire d’habilitation à diriger des recherches, Université Diderot -- Paris 7. Available at arXiv:1201.0856.

[6]

M. Bodirsky, P. Jonsson, and T. V. Pham. 2017. The complexity of phylogeny constraint satisfaction problems. ACM Transactions on Computational Logic 18, 3 (2017), 23:1--23:42.

Digital Library

[7]

M. Bodirsky and J. Kára. 2008. The complexity of equality constraint languages. Theory of Computing Systems 43, 2 (Aug. 2008), 136--158.

Digital Library

[8]

M. Bodirsky and J. Kára. 2010. The complexity of temporal constraint satisfaction problems. Journal of the ACM 57, 2, Article 9 (2010), 41 pages.

Digital Library

[9]

M. Bodirsky and M. Pinsker. 2015. Schaefer’s theorem for graphs. Journal of the ACM 62, 3, Article 19 (June 2015), 52 pages.

Digital Library

[10]

V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras. I. Cybernetics 5, 3 (1969), 243--252.

[11]

V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras. II. Cybernetics 5, 5 (1969), 531--539.

[12]

E. Böhler, E. Hemaspaandra, S. Reith, and H. Vollmer. 2002. Equivalence and isomorphism for Boolean constraint satisfaction. In Proceedings of the 16th International Workshop on Computer Science Logic (CSL’02). Springer Berlin, Berlin, 412--426.

[13]

F. Börner. 2008. Basics of Galois connections. In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer (Eds.). Lecture Notes in Computer Science, Vol. 5250. Springer Berlin, 38--67.

[14]

A. Bulatov. 2011. Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic 12, 4, Article 24 (July 2011), 66 pages.

Digital Library

[15]

A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS’17). IEEE Computer Society, 319--330.

[16]

A. Bulatov and A. Hedayaty. 2012. Counting problems and clones of functions. Multiple-Valued Logic and Soft Computing 18, 2 (2012), 117--138.

[17]

A. Bulatov, P. Jeavons, and A. Krokhin. 2005. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing 34, 3 (March 2005), 720--742.

Digital Library

[18]

C. Calabro, R. Impagliazzo, and R. Paturi. 2009. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, J. Chen and F. V. Fomin (Eds.). Lecture Notes in Computer Science, Vol. 5917. Springer Berlin, 75--85.

[19]

C. Carbonnel and M. C. Cooper. 2016. Tractability in constraint satisfaction problems: a survey. Constraints 21, 2 (Apr. 2016), 115--144.

Digital Library

[20]

M. C. Cooper and S. Zǐvný. 2017. Hybrid tractable classes of constraint problems. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zǐvný (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 113--135.

[21]

N. Creignou, U. Egly, and J. Schmidt. 2014. Complexity Classifications for Logic-Based Argumentation. ACM Transactions on Computational Logic 15, 3 (2014), 19:1--19:20.

Digital Library

[22]

M. Cygan, F. V. Fomin, A. Golovnev, A. S. Kulikov, I. Mihajlin, J. Pachocki, and A. Socała. 2016. Tight bounds for graph homomorphism and subgraph isomorphism. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). Society for Industrial and Applied Mathematics, Philadelphia, PA, 1643--1649.

[23]

R. de Haan, I. A. Kanj, and S. Szeider. 2015. On the subexponential-time complexity of CSP. Journal of Artificial Intelligence Research (JAIR) 52 (2015), 203--234.

Digital Library

[24]

T. Feder and M. Y. Vardi. 1998. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing 28, 1 (1998), 57--104.

Digital Library

[25]

R. V. Freivald. 1966. A completeness criterion for partial functions of logic and many-valued logic algebras. Soviet Physics Doklady 11 (Oct. 1966), 288.

[26]

D. Geiger. 1968. Closed systems of functions and predicates. Pacific Journal on Mathematics 27, 1 (1968), 95--100.

[27]

M. Grohe. 2006. The structure of tractable constraint satisfaction problems. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS’06). Springer Berlin, Berlin,58--72.

Digital Library

[28]

L. Ham. 2017. Gap theorems for robust satisfiability: Boolean CSPs and beyond. Theoretical Computer Science 676 (2017), 69--91.

[29]

T. Hertli. 2014. 3-SAT faster and simpler - Unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing 43, 2 (2014), 718--729.

[30]

R. Impagliazzo and R. Paturi. 2001. On the complexity of k-SAT. Journal of Computer and System Sciences 62, 2 (2001), 367--375.

Digital Library

[31]

R. Impagliazzo, R. Paturi, and F. Zane. 2001. Which problems have strongly exponential complexity?Journal of Computer and System Sciences 63, 4 (2001), 512--530.

[32]

P. Jeavons. 1998. On the algebraic structure of combinatorial problems. Theoretical Computer Science 200 (1998), 185--204.

Digital Library

[33]

P. Jeavons, D. A. Cohen, and M. Gyssens. 1999. How to determine the expressive power of constraints. Constraints 4, 2 (1999), 113--131.

Digital Library

[34]

P. Jonsson and V. Lagerkvist. 2017. An initial study of time complexity in infinite-domain constraint satisfaction. Artificial Intelligence 245 (2017), 115--133.

[35]

P. Jonsson, V. Lagerkvist, G. Nordh, and B. Zanuttini. 2017. Strong partial clones and the time complexity of SAT problems. Journal of Computer and System Sciences 84 (2017), 52--78.

Digital Library

[36]

V. Lagerkvist. 2015. Precise upper and lower bounds for the monotone constraint satisfaction problem. In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS’15). Springer Berlin, Berlin, 357--368.

[37]

R. Pöschel. 2004. Galois connections for operations and relations. In Galois Connections and Applications, K. Denecke, M. Erné, and S.L. Wismath (Eds.). Mathematics and Its Applications, Vol. 565. Springer Netherlands, 231--258.

[38]

E. Post. 1941. The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies 5 (1941), 1--122.

[39]

B. A. Romov. 1981. The algebras of partial functions and their invariants. Cybernetics 17, 2 (1981), 157--167.

[40]

B. A. Romov. 2006. The completeness problem in partial hyperclones. Discrete Mathematics 306, 13 (July 2006), 1405--1414.

Digital Library

[41]

F. Rossi, P. van Beek, and T. Walsh (Eds.). 2006. Handbook of Constraint Programming. Foundations of Artificial Intelligence, Vol. 2. Elsevier.

Digital Library

[42]

S. J. Russell and P. Norvig. 2010. Artificial Intelligence - A Modern Approach (3rd internat. ed.). Pearson Education.

[43]

T. Schaefer. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory Of Computing (STOC’78). ACM Press, 216--226.

Digital Library

[44]

H. Schnoor and I. Schnoor. 2008. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer (Eds.). Lecture Notes in Computer Science, Vol. 5250. Springer Berlin Heidelberg, 229--254.

[45]

K. Schölzel. 2015. Dichotomy on intervals of strong partial Boolean clones. Algebra Universalis 73, 3--4 (2015), 347--368.

[46]

M. Wahlström. 2007. Algorithms, Measures and Upper Bounds for Satisfiability and Related Problems. Ph.D. Dissertation. Linköping University.

[47]

D. Zhuk. 2017. The proof of CSP dichotomy conjecture. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS’17). IEEE Computer Society, 331--342.

Cited By

Jonsson PLagerkvist V(2022)General Lower Bounds and Improved Algorithms for Infinite–Domain CSPsAlgorithmica10.1007/s00453-022-01017-885:1(188-215)Online publication date: 11-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-01017-8
Arvind VGuruswami V(2022)CNF Satisfiability in a Subspace and Related ProblemsAlgorithmica10.1007/s00453-022-00958-484:11(3276-3299)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s00453-022-00958-4
Lagerkvist VWahlström M(2021)The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP ProblemsACM Transactions on Computation Theory10.1145/349233614:1(1-54)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3492336
Show More Cited By

Index Terms

Fine-Grained Time Complexity of Constraint Satisfaction Problems
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
    2. Problems, reductions and completeness
  2. Design and analysis of algorithms
    1. Parameterized complexity and exact algorithms

Recommendations

Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
We study the fine-grained complexity of NP-complete satisfiability (SAT) problems and constraint satisfaction problems (CSPs) in the context of the strong exponential-time hypothesis(SETH), showing non-trivial lower and upper bounds on the running time. ...
Full Constraint Satisfaction Problems

Feder and Vardi have conjectured that all constraint satisfaction problems to a fixed structure (constraint language) are polynomial or NP-complete. This so-called dichotomy conjecture remains open, although it has been proved in a number of special ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 13, Issue 1

March 2021

143 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/3447816

Editor:
Ryan O’Donnell
Carnegie Mellon University, USA

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 2021

Accepted: 01 September 2020

Revised: 01 September 2020

Received: 01 November 2019

Published in TOCT Volume 13, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Vetenskapsrådet

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
92
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jonsson PLagerkvist V(2022)General Lower Bounds and Improved Algorithms for Infinite–Domain CSPsAlgorithmica10.1007/s00453-022-01017-885:1(188-215)Online publication date: 11-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-01017-8
Arvind VGuruswami V(2022)CNF Satisfiability in a Subspace and Related ProblemsAlgorithmica10.1007/s00453-022-00958-484:11(3276-3299)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s00453-022-00958-4
Lagerkvist VWahlström M(2021)The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP ProblemsACM Transactions on Computation Theory10.1145/349233614:1(1-54)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3492336
Jonsson PLagerkvist VSchmidt JUppman H(2021)The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problemsTheoretical Computer Science10.1016/j.tcs.2021.09.006892(1-24)Online publication date: Nov-2021
https://doi.org/10.1016/j.tcs.2021.09.006

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents