article

The Complexity of Equality Constraint Languages

Authors:

Manuel Bodirsky,

Jan KáraAuthors Info & Claims

Theory of Computing Systems, Volume 43, Issue 2

Pages 136 - 158

https://doi.org/10.1007/s00224-007-9083-9

Published: 07 April 2008 Publication History

Abstract

We classify the computational complexity of all constraint satisfaction problems where the constraint language is preserved by all permutations of the domain. A constraint language is preserved by all permutations of the domain if and only if all the relations in the language can be defined by boolean combinations of the equality relation. We call the corresponding constraint languages equality constraint languages.

For the classification result we apply the universal-algebraic approach to infinite-valued constraint satisfaction, and show that an equality constraint language is tractable if it admits a constant unary polymorphism or an injective binary polymorphism, and is NP-complete otherwise. We also discuss how to determine algorithmically whether a given constraint language is tractable.

Cited By

View all

Bodirsky MSemanišinová ŽLutz CSobocinski PLago UEsparza J(2024)The Complexity of Resilience Problems via Valued Constraint Satisfaction ProblemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662071(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662071
Bodirsky MBodor B(2024)A Complexity Dichotomy in Spatial Reasoning via Ramsey TheoryACM Transactions on Computation Theory10.1145/364944516:2(1-39)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3649445
Jonsson PLagerkvist V(2023)General Lower Bounds and Improved Algorithms for Infinite–Domain CSPsAlgorithmica10.1007/s00453-022-01017-885:1(188-215)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s00453-022-01017-8
Show More Cited By

Index Terms

The Complexity of Equality Constraint Languages

Recommendations

The complexity of equality constraint languages
CSR'06: Proceedings of the First international computer science conference on Theory and Applications

We apply the algebraic approach to infinite-valued constraint satisfaction to classify the computational complexity of all constraint satisfaction problems with templates that have a highly transitive automorphism group. A relational structure has such ...
Datalog and constraint satisfaction with infinite templates

On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this connection for infinite structures. This has applications ...
The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case

The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logical sentence consisting of a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Theory of Computing Systems Volume 43, Issue 2

April 2008

195 pages

ISSN:1432-4350

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bodirsky MSemanišinová ŽLutz CSobocinski PLago UEsparza J(2024)The Complexity of Resilience Problems via Valued Constraint Satisfaction ProblemsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662071(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662071
Bodirsky MBodor B(2024)A Complexity Dichotomy in Spatial Reasoning via Ramsey TheoryACM Transactions on Computation Theory10.1145/364944516:2(1-39)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3649445
Jonsson PLagerkvist V(2023)General Lower Bounds and Improved Algorithms for Infinite–Domain CSPsAlgorithmica10.1007/s00453-022-01017-885:1(188-215)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s00453-022-01017-8
Bodirsky MRydval J(2022)On the Descriptive Complexity of Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/356605170:1(1-58)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3566051
Jonsson PLagerkvist VRoy B(2021)Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory10.1145/343438713:1(1-32)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434387
Bodirsky MBodor BGorla D(2021)Canonical polymorphisms of ramsey structures and the unique interpolation propertyProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470683(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470683
Wrona MHermanns HZhang LKobayashi NMiller D(2020)On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict WidthProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3373718.3394781(958-971)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3373718.3394781
Barto LKompatscher MOlšák MVan Pham TPinsker MAceto LIngólfsdóttir A(2017)The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problemsProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330063(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330063
Bodirsky MJonsson PPham T(2017)The Complexity of Phylogeny Constraint Satisfaction ProblemsACM Transactions on Computational Logic10.1145/310590718:3(1-42)Online publication date: 2-Aug-2017
https://dl.acm.org/doi/10.1145/3105907
Bodirsky MMottet AKoskinen EGrohe MShankar N(2016)Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfactionProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2934515(623-632)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2933575.2934515
Show More Cited By

View Options

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.

Abstract

Cited By

Index Terms

Recommendations