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)

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

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)