Discrete Temporal Constraint Satisfaction Problems
Copyright policy )Discrete Temporal Constraint Satisfaction Problems
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.
FOS: Computer and information sciences, Discrete linear orders, Successor relation, Mathematics - Logic, Computational Complexity (cs.CC), Computer Science - Computational Complexity, Presburger arithmetic, Endomorphisms, FOS: Mathematics, Integers, F.4.1, Polymorphisms, Logic (math.LO), 03C99
FOS: Computer and information sciences, Discrete linear orders, Successor relation, Mathematics - Logic, Computational Complexity (cs.CC), Computer Science - Computational Complexity, Presburger arithmetic, Endomorphisms, FOS: Mathematics, Integers, F.4.1, Polymorphisms, Logic (math.LO), 03C99
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!