Computational complexity of linear constraints over the integers

DOI10.1016/J.ARTINT.2012.10.001MaRDI QIDQ360099zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Tomas Lööw

Publication date 26 August 2013

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0004370212001221

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A unifying approach to temporal constraint reasoning
• Complexity classification in qualitative temporal constraint reasoning
• scientific article; zbMATH DE number 1234563
• Point algebras for temporal reasoning: Algorithms and complexity
• Discrete temporal constraint satisfaction problems

Cited in

(14)

• Tropically convex constraint satisfaction
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• MAX-closed semilinear constraint satisfaction
• Propagating systems of dense linear integer constraints
• Constraint satisfaction problems over numeric domains
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Constraint satisfaction problems over the integers with successor
• Tractability conditions for numeric CSPs
• scientific article; zbMATH DE number 7378350 (Why is no real title available?)
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• An interdisciplinary experimental evaluation on the disjunctive temporal problem
• A complexity perspective on entailment of parameterized linear constraints
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning

This page was built for publication: Computational complexity of linear constraints over the integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q360099)