Tractability conditions for numeric CSPs
type: Item
instance of: scholarly article
title: Tractability conditions for numeric CSPs
zbMATH Open document ID: 1386.68071
author: Peter Jonsson
author: Johan Thapper
published in: Theoretical Computer Science
publication date: 2018-02-09T00:00:00Z
full work available at URL: jt18tcs-preprint.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03C64
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 14P10
zbMATH DE Number: 6836575
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: semialgebraic constraint
zbMATH Keywords: o-minimality
zbMATH Keywords: algebraic variety
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
OpenAlex ID: W2791591692
cites work: Polynomial algorithms for linear programming over the algebraic numbers
cites work: On the Complexity of Numerical Analysis
cites work: Algorithms in real algebraic geometry
cites work: Non-dichotomies in Constraint Satisfaction Complexity
cites work: Essential Convexity and Complexity of Semi-Algebraic Constraints
cites work: Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
cites work: The complexity of temporal constraint satisfaction problems
cites work: The complexity of surjective homomorphism problems-a survey
cites work: Max-Closed Semilinear Constraint Satisfaction
cites work: Constraint Satisfaction Problems over Numeric Domains
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: A Decision Procedure for the First Order Theory of Real Addition with Order
cites work: Q4155835
cites work: Q4821338
cites work: Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets
cites work: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
cites work: On the algebraic structure of combinatorial problems
cites work: Computational complexity of linear constraints over the integers
cites work: Affine Consistency and the Complexity of Semilinear Constraints
cites work: Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
cites work: Q3999699
cites work: The Computational Complexity of Simultaneous Diophantine Approximation Problems
cites work: Q4513933
cites work: Model Theory
cites work: An exact duality theory for semidefinite programming and its complexity implications
cites work: Complexity of Some Geometric and Topological Problems
cites work: Fixed points, Nash equilibria, and the existential theory of the reals
cites work: The complexity of satisfiability problems
cites work: Q5807665
cites work: Q4392286
DOI: 10.1016/J.TCS.2018.01.013
description: scientific article; zbMATH DE number 6836575