Publication details for Dr Barnaby MartinBodirsky, Manuel, Martin, Barnaby & Mottet, Antoine (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM 65(2): 9.
- Publication type: Journal Article
- ISSN/ISBN: 0004-5411, 1535-9921
- DOI: 10.1145/3154832
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.