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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (522Kb)
|Publisher Web site:||https://doi.org/10.1145/3154832|
|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, https://doi.org/10.1145/10.1145/3154832.|
|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|