Tractability conditions for numeric CSPs

DOI10.1016/j.tcs.2018.01.013zbMath1386.68071OpenAlexW2791591692MaRDI QIDQ683751

Peter Jonsson, Johan Thapper

Publication date: 9 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01796723/file/jt18tcs-preprint.pdf

zbMATH Keywords

computational complexityo-minimalityconstraint satisfaction problemalgebraic varietysemialgebraic constraint

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Semialgebraic sets and related spaces (14P10) Model theory of ordered structures; o-minimality (03C64)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Computational complexity of linear constraints over the integers
• The complexity of surjective homomorphism problems-a survey
• Fixed points, Nash equilibria, and the existential theory of the reals
• On the algebraic structure of combinatorial problems
• Polynomial algorithms for linear programming over the algebraic numbers
• An exact duality theory for semidefinite programming and its complexity implications
• Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction
• Affine Consistency and the Complexity of Semilinear Constraints
• Essential Convexity and Complexity of Semi-Algebraic Constraints
• Non-dichotomies in Constraint Satisfaction Complexity
• Complexity of Some Geometric and Topological Problems
• Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets
• The complexity of temporal constraint satisfaction problems
• On the Complexity of Numerical Analysis
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• A Decision Procedure for the First Order Theory of Real Addition with Order
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Model Theory
• Constraint Satisfaction Problems over Numeric Domains
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Max-Closed Semilinear Constraint Satisfaction
• Algorithms in real algebraic geometry