Tractability conditions for numeric CSPs

DOI10.1016/J.TCS.2018.01.013MaRDI QIDQ683751zbMATH OpenOpenAlexFDO

Authors 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

algebraic varietycomputational complexityconstraint satisfaction problemo-minimalitysemialgebraic constraint

Mathematics Subject Classification ID

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

Recommendations

• Affine consistency and the complexity of semilinear constraints
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Constraint satisfaction problems over numeric domains
• Essential convexity and complexity of semi-algebraic constraints
• Semilinear Program Feasibility

Cites work

• A Decision Procedure for the First Order Theory of Real Addition with Order
• Affine consistency and the complexity of semilinear constraints
• Algorithms in real algebraic geometry
• An exact duality theory for semidefinite programming and its complexity implications
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity of some geometric and topological problems
• Computational complexity of linear constraints over the integers
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Constraint satisfaction problems over numeric domains
• Essential convexity and complexity of semi-algebraic constraints
• Fixed points, Nash equilibria, and the existential theory of the reals
• Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
• scientific article; zbMATH DE number 49991 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• scientific article; zbMATH DE number 1531891 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• MAX-closed semilinear constraint satisfaction
• Model Theory
• Non-dichotomies in Constraint Satisfaction Complexity
• On the algebraic structure of combinatorial problems
• On the Complexity of Numerical Analysis
• Polynomial algorithms for linear programming over the algebraic numbers
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
• The complexity of satisfiability problems
• The complexity of surjective homomorphism problems-a survey
• The complexity of temporal constraint satisfaction problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(6)

• Tropically convex constraint satisfaction
• Affine consistency and the complexity of semilinear constraints
• Essential convexity and complexity of semi-algebraic constraints
• Semilinear Program Feasibility
• Constraint satisfaction problems over numeric domains
• MAX-closed semilinear constraint satisfaction

This page was built for publication: Tractability conditions for numeric CSPs

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