Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Fine-Grained Time Complexity of Constraint Satisfaction Problems

Fine-Grained Time Complexity of Constraint Satisfaction Problems 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 SD such that the time complexity of the NP-complete problem CSP(SD) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP(SD) strictly decreases when D increases (unless the ETH is false) and provide stronger complexity results in the special case when D=3. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Fine-Grained Time Complexity of Constraint Satisfaction Problems

Download PDF
32 pages

Loading next page...
 
/lp/association-for-computing-machinery/fine-grained-time-complexity-of-constraint-satisfaction-problems-M5nFH0QlnZ
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3434387
Publisher site
See Article on Publisher Site

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 SD such that the time complexity of the NP-complete problem CSP(SD) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP(SD) strictly decreases when D increases (unless the ETH is false) and provide stronger complexity results in the special case when D=3.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jan 21, 2021

Keywords: Constraint satisfaction problems

References

  • On some closed classes in partial two-valued logic
    Alekseev, V. B.; Voronenko, A. A.
  • The constraint satisfaction problem and universal algebra
    Barto, L.
  • The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
    Barto, L.; Pinsker, M.
  • Minimal distance of propositional models
    Behrisch, M.; Hermann, M.; Mengel, S.; Salzer, G.
  • Complexity classification in infinite-domain constraint satisfaction
    Bodirsky, M.
  • The complexity of phylogeny constraint satisfaction problems
    Bodirsky, M.; Jonsson, P.; Pham, T. V.
  • The complexity of equality constraint languages
    Bodirsky, M.; Kára, J.
  • The complexity of temporal constraint satisfaction problems
    Bodirsky, M.; Kára, J.
  • Schaefer’s theorem for graphs
    Bodirsky, M.; Pinsker, M.
  • Galois theory for Post algebras
    Bodnarchuk, V. G.; Kaluzhnin, L. A.; Kotov, V. N.; Romov, B. A.
  • Galois theory for Post algebras
    Bodnarchuk, V. G.; Kaluzhnin, L. A.; Kotov, V. N.; Romov, B. A.
  • Equivalence and isomorphism for Boolean constraint satisfaction
    Böhler, E.; Hemaspaandra, E.; Reith, S.; Vollmer, H.
  • Basics of Galois connections
    Börner, F.
  • Complexity of conservative constraint satisfaction problems
    Bulatov, A.
  • A dichotomy theorem for nonuniform CSPs
    Bulatov, A.
  • Counting problems and clones of functions
    Bulatov, A.; Hedayaty, A.
  • Classifying the complexity of constraints using finite algebras
    Bulatov, A.; Jeavons, P.; Krokhin, A.
  • The complexity of satisfiability of small depth circuits
    Calabro, C.; Impagliazzo, R.; Paturi, R.
  • Tractability in constraint satisfaction problems: a survey
    Carbonnel, C.; Cooper, M. C.
  • Hybrid tractable classes of constraint problems
    Cooper, M. C.; Zǐvný, S.
  • Complexity Classifications for Logic-Based Argumentation
    Creignou, N.; Egly, U.; Schmidt, J.
  • Tight bounds for graph homomorphism and subgraph isomorphism
    Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A.
  • On the subexponential-time complexity of CSP
    de Haan, R.; Kanj, I. A.; Szeider, S.
  • The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory
    Feder, T.; Vardi, M. Y.
  • A completeness criterion for partial functions of logic and many-valued logic algebras
    Freivald, R. V.
  • Closed systems of functions and predicates
    Geiger, D.
  • The structure of tractable constraint satisfaction problems
    Grohe, M.
  • Gap theorems for robust satisfiability: Boolean CSPs and beyond
    Ham, L.
  • 3-SAT faster and simpler - Unique-SAT bounds for PPSZ hold in general
    Hertli, T.
  • On the complexity of k-SAT
    Impagliazzo, R.; Paturi, R.
  • Which problems have strongly exponential complexity?Journal of Computer and System Sciences 63, 4 (2001), 512--530
    Impagliazzo, R.; Paturi, R.; Zane, F.
  • On the algebraic structure of combinatorial problems
    Jeavons, P.
  • How to determine the expressive power of constraints
    Jeavons, P.; Cohen, D. A.; Gyssens, M.
  • An initial study of time complexity in infinite-domain constraint satisfaction
    Jonsson, P.; Lagerkvist, V.
  • Strong partial clones and the time complexity of SAT problems
    Jonsson, P.; Lagerkvist, V.; Nordh, G.; Zanuttini, B.
  • Precise upper and lower bounds for the monotone constraint satisfaction problem
    Lagerkvist, V.
  • Galois connections for operations and relations
    Pöschel, R.
  • The two-valued iterative systems of mathematical logic
    Post, E.
  • The algebras of partial functions and their invariants
    Romov, B. A.
  • The completeness problem in partial hyperclones
    Romov, B. A.
  • Handbook of Constraint Programming
    Rossi, F.; van Beek, P.; (Eds, T. Walsh
  • Artificial Intelligence - A Modern Approach (3rd internat
    Russell, S. J.; Norvig, P.
  • The complexity of satisfiability problems
    Schaefer, T.
  • Partial polymorphisms and constraint satisfaction problems
    Schnoor, H.; Schnoor, I.
  • Dichotomy on intervals of strong partial Boolean clones
    Schölzel, K.
  • Algorithms, Measures and Upper Bounds for Satisfiability and Related Problems
    Wahlström, M.
  • The proof of CSP dichotomy conjecture
    Zhuk, D.