Discrete Temporal Constraint Satisfaction Problems
Discrete Temporal Constraint Satisfaction Problems
复制标题
DOI：
10.1145/3154832
复制
发表时间：
2018-03-01
影响因子：
2.5
通讯作者：
Mottet, Antoine
中科院分区：
文献类型：
--
作者：
Bodirsky, Manuel;Martin, Barnaby;Mottet, Antoine
离散时间约束满足问题（英语：Discrete temporal constraint satisfaction problem，缩写为CSP）是一个在整数集合上的约束满足问题，其约束语言由一阶可定义的关系组成。我们证明了每一个离散时间CSP是P或NP-完全的，除非它可以制定为有限域CSP，在这种情况下，计算复杂性是不知道的一般。
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.