Skip to main content

Research Repository

Advanced Search

Discrete Temporal Constraint Satisfaction Problems

Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine

Discrete Temporal Constraint Satisfaction Problems Thumbnail


Authors

Manuel Bodirsky

Antoine Mottet



Abstract

A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every discrete temporal CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP, in which case the computational complexity is not known in general.

Citation

Bodirsky, M., Martin, B., & Mottet, A. (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM, 65(2), Article 9. https://doi.org/10.1145/3154832

Journal Article Type Article
Acceptance Date Nov 7, 2017
Online Publication Date Feb 6, 2018
Publication Date Mar 1, 2018
Deposit Date Nov 12, 2017
Publicly Available Date Mar 29, 2024
Journal Journal of the Association for Computing Machinery.
Print ISSN 0004-5411
Electronic ISSN 1557-735X
Publisher Association for Computing Machinery (ACM)
Peer Reviewed Peer Reviewed
Volume 65
Issue 2
Article Number 9
DOI https://doi.org/10.1145/3154832

Files

Accepted Journal Article (534 Kb)
PDF

Copyright Statement
© 2018 ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Journal of the ACM, https://doi.org/10.1145/10.1145/3154832.





You might also like



Downloadable Citations