research-article

The complexity of temporal constraint satisfaction problems

Authors:

Manuel Bodirsky,

Jan KaraAuthors Info & Claims

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Pages 29 - 38

https://doi.org/10.1145/1374376.1374382

Published: 17 May 2008 Publication History

Abstract

A temporal constraint language is a set of relations that has a first-order definition in (b Q,<), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal constraint languages: if the constraint language is contained in one out of nine temporal constraint languages, then the CSP can be solved in polynomial time; otherwise, the CSP is NP-complete. Our proof combines model-theoretic concepts with techniques from universal algebra, and also applies the so-called product Ramsey theorem, which we believe will be useful in similar contexts of constraint satisfaction complexity classification.

References

[1]

M. Bodirsky: Cores of countably categorical structures. Logical Methods in Computer Science (LMCS), 2007.

[2]

M. Bodirsky and V. Dalmau: Datalog and constraint satisfaction with infinite templates. In Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS'06), LNCS 3884, pages 646-659. Springer Verlag, 2006.

Digital Library

[3]

M. Bodirsky and J. Kara: The complexity of equality constraint languages. Accepted for publication in Theory of Computing Systems, 2007.A conference version of the paper appeared in the proceedings of the International Computer Science Symposium in Russia (CSR'06).

[4]

M. Bodirsky and J. Kara: A fast algorithm and lower bound for temporal reasoning. Preprint.

[5]

M. Bodirsky and J. Nesetril: Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation, 16(3):359--373, 2006.

Digital Library

[6]

V. G. Bodnarcuk, L. A. Kaluznin, V. N. Kotov, and B. A. Romov: Galois theory for post algebras, part I and II. Cybernetics, 5:243--539, 1969.

[7]

A. Bulatov: A dichotomy theorem for constraints on a three-element set. In FOCS'02, 649--658, 2002.

Digital Library

[8]

A. Bulatov: A graph of a relational structure and constraint satisfaction problems.In Proceedings of the 19th IEEE Annual Symposium on Logic in Computer Science (LICS'04), Turku, Finland, 2004.

Digital Library

[9]

A. Bulatov, P. Jeavons, and A. Krokhin: The complexity of constraint satisfaction: An algebraic approach (a survey paper). In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics, Chemistry, 207:181--213, 2005.

[10]

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

Digital Library

[11]

P. J. Cameron: Transitivity of permutation groups on unordered sets. Math. Z., 148:127--139, 1976.

[12]

D. A. Cohen, P. Jeavons, P. Jonsson, and M. Koubarakis: Building tractable disjunctive constraints. J. ACM, 47(5):826--853, 2000.

Digital Library

[13]

N. Creignou, S. Khanna, and M. Sudan: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications 7, 2001.

Digital Library

[14]

V. Dalmau and J. Pearson: Closure functions and width 1 problems. CP'99, pages 159--173, 1999.

Digital Library

[15]

T. Feder and M. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28:57--104, 1999.

Digital Library

[16]

M. Garey and D. Johnson: A guide to NP-completeness. CSLI Press, 1978.

[17]

D. Geiger: Closed systems of functions and predicates. Pacific Journal of Mathematics, 27:95--100, 1968.

[18]

W. Hodges: A shorter model theory. Cambridge University Press, 1997.

Digital Library

[19]

P. M. Idziak, P. Markovic, R. McKenzie, M. Valeriote, and R. Willard: Tractability and learnability arising from algebras with few subpowers. In LICS'07, pages 213--224, 2007.

Digital Library

[20]

P. Jeavons, D. Cohen, and M. Gyssens: Closure properties of constraints. JACM, 44(4):527--548, 1997.

Digital Library

[21]

H. Kautz, P. van Beek, and M. Vilain: Constraint propagation algorithms: A revised report. Qualitative Reasoning about Physical Systems, pages 373--381, 1990.

Digital Library

[22]

B. Nebel and H.-J. Burckert: Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. JACM, 42(1):43--66, 1995.

Digital Library

[23]

P. G. Jeavons and M. C. Cooper: Tractable constraints on ordered domains. Artificial Intelligence, 79(2):327--339, 1995.

Digital Library

[24]

R. L. Graham, B. L. Rothschild, and J. H. Spencer: Ramsey theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., 1990. Second edition.

Digital Library

[25]

T. J. Schaefer: The complexity of satisfiability problems. In Proceedings of STOC'78, pages 216--226, 1978.

Digital Library

[26]

A. Szendrei: Clones in universal Algebra. Seminaire de mathematiques superieures. Les Presses de L'Universite de Montreal, 1986.

Cited By

Mottet APinsker M(2022)Smooth approximations and CSPs over finitely bounded homogeneous structuresProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533353(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533353
Bodirsky M(2018)Finite Relation Algebras with Normal RepresentationsRelational and Algebraic Methods in Computer Science10.1007/978-3-030-02149-8_1(3-17)Online publication date: 6-Oct-2018
https://doi.org/10.1007/978-3-030-02149-8_1
Bodirsky MChen HPinsker M(2014)The reducts of equality up to primitive positive interdefinabilityThe Journal of Symbolic Logic10.2178/jsl/128619814675:4(1249-1292)Online publication date: 12-Mar-2014
https://doi.org/10.2178/jsl/1286198146
Show More Cited By

Index Terms

The complexity of temporal constraint satisfaction problems
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

The complexity of temporal constraint satisfaction problems

A temporal constraint language is a set of relations that has a first-order definition in(Q;<), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal ...
The complexity of constraint satisfaction games and QCSP

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to ...
Stochastic search versus genetic algorithms for solving real time and over-constrained temporal constraint problems

The aim of this work is to study the applicability of Genetic Algorithms (GAs) and stochastic local search methods to solve real time and over constrained temporal constraint problems. Solving these two type of problems consists of finding a possible ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

May 2008

712 pages

ISBN:9781605580470

DOI:10.1145/1374376

General Chair:
Richard Ladner
University of Washington
,
Program Chair:
Cynthia Dwork
Microsoft Research, Silicon Valley

Copyright © 2008 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 ACM 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '08

Sponsor:

STOC '08: Symposium on Theory of Computing

May 17 - 20, 2008

British Columbia, Victoria, Canada

Acceptance Rates

STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
308
Total Downloads

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

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mottet APinsker M(2022)Smooth approximations and CSPs over finitely bounded homogeneous structuresProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533353(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533353
Bodirsky M(2018)Finite Relation Algebras with Normal RepresentationsRelational and Algebraic Methods in Computer Science10.1007/978-3-030-02149-8_1(3-17)Online publication date: 6-Oct-2018
https://doi.org/10.1007/978-3-030-02149-8_1
Bodirsky MChen HPinsker M(2014)The reducts of equality up to primitive positive interdefinabilityThe Journal of Symbolic Logic10.2178/jsl/128619814675:4(1249-1292)Online publication date: 12-Mar-2014
https://doi.org/10.2178/jsl/1286198146
Wrona M(2012)Syntactically Characterizing Local-to-Global Consistency in ORD-HornProceedings of the 18th International Conference on Principles and Practice of Constraint Programming - Volume 751410.5555/2969951.2970007(704-719)Online publication date: 8-Oct-2012
https://dl.acm.org/doi/10.5555/2969951.2970007
Chen HWrona M(2012)Guarded Ord-HornProceedings of the 2012 19th International Symposium on Temporal Representation and Reasoning10.1109/TIME.2012.19(99-106)Online publication date: 12-Sep-2012
https://dl.acm.org/doi/10.1109/TIME.2012.19
Bodirsky MDalmau VMartin BPinsker M(2010)Distance constraint satisfaction problemsProceedings of the 35th international conference on Mathematical foundations of computer science10.5555/1885577.1885593(162-173)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1885577.1885593
Bodirsky MKára J(2010)A fast algorithm and datalog inexpressibility for temporal reasoningACM Transactions on Computational Logic10.1145/1740582.174058311:3(1-21)Online publication date: 18-May-2010
https://dl.acm.org/doi/10.1145/1740582.1740583
Bodirsky MHils MMartin B(2010)On the Scope of the Universal-Algebraic Approach to Constraint SatisfactionProceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer Science10.1109/LICS.2010.13(90-99)Online publication date: 11-Jul-2010
https://dl.acm.org/doi/10.1109/LICS.2010.13
Goerdt A(2010)On random betweenness constraintsCombinatorics, Probability and Computing10.1017/S096354831000031319:5-6(775-790)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1017/S0963548310000313
Goerdt A(2009)On random betweenness constraintsProceedings of the 17th international conference on Fundamentals of computation theory10.5555/1789494.1789511(157-168)Online publication date: 2-Sep-2009
https://dl.acm.org/doi/10.5555/1789494.1789511
Show More Cited By

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents