We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Discrete temporal constraint satisfaction problems.

Bodirsky, Manuel and Martin, Barnaby and Mottet, Antoine (2018) 'Discrete temporal constraint satisfaction problems.', Journal of the ACM., 65 (2). p. 9.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher 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,
Date accepted:07 November 2017
Date deposited:13 November 2017
Date of first online publication:06 February 2018
Date first made open access:06 February 2018

Save or Share this output

Look up in GoogleScholar