# On Classifying Continuous Constraint Satisfaction Problems

arXiv: https://arxiv.org/abs/2106.02397 · HTML: https://mlsanity.com/paper/2106.02397/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 66 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 14 of 14)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Smoothing the gap between NP and ER](https://mlsanity.com/paper/1912.02278/) (2019)
- [Intersection Graphs of Rays and Grounded Segments](https://mlsanity.com/paper/1612.03638/) (2016)
- [The Complexity of Drawing a Graph in a Polygonal Region](https://mlsanity.com/paper/1802.06699/) (2018)
- [A Universality Theorem for Nested Polytopes](https://mlsanity.com/paper/1908.02213/) (2019)
- [Dynamic Toolbox for ETRINV](https://mlsanity.com/paper/1912.08674/) (2019)
- [On the Computational Complexity of Decision Problems about Multi-Player Nash Equilibria](https://mlsanity.com/paper/2001.05196/) (2020)
- [Recognition and Complexity of Point Visibility Graphs](https://mlsanity.com/paper/1503.07082/) (2015)
- [On Restricted Nonnegative Matrix Factorization](https://mlsanity.com/paper/1605.07061/) (2016)
- [Approximating the Existential Theory of the Reals](https://mlsanity.com/paper/1810.01393/) (2018)
- [A Practical Algorithm with Performance Guarantees for the Art Gallery Problem](https://mlsanity.com/paper/2007.06920/) (2020)
- [How do exponential size solutions arise in semidefinite programming?](https://mlsanity.com/paper/2103.00041/) (2021)
- [The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains](https://mlsanity.com/paper/2007.01779/) (2020)
- [The complete classification for quantified equality constraints](https://mlsanity.com/paper/2104.00406/) (2021)

## Built on by (most cited first, 5 of 5)

- [Trust the PRoC3S: Solving Long-Horizon Robotics Problems with LLMs and Constraint Satisfaction](https://mlsanity.com/paper/2406.05572/) (2024)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [The Hardness of Reasoning about Probabilities and Causality](https://mlsanity.com/paper/2305.09508/) (2023)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [MiranDa: Mimicking the Learning Processes of Human Doctors to Achieve Causal Inference for Medication Recommendation](https://mlsanity.com/paper/2408.01445/) (2024)

## Abstract (arXiv)

A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain U subset ℝ. We engage in a systematic study to classify CCSPs that are complete of the Existential Theory of the Reals, i.e., ER-complete. To define this class, we first consider the problem ETR, which also stands for Existential Theory of the Reals. In an instance of this problem we are given some sentence of the form exists x1, ldots, xn ∈ ℝ : Phi(x1, ldots, xn), where Phi is a well-formed quantifier-free formula consisting of the symbols 0, 1, +, ·, ≥, >, wedge, vee, neg, the goal is to check whether this sentence is true. Now the class ER is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP subseteq ER subseteq PSPACE. We restrict our attention on CCSPs with addition constraints (x + y = z) and some other mild technical conditions. Previously, it was shown that multiplication constraints (x · y = z), squaring constraints (x2 = y), or inversion constraints (x· y = 1) are sufficient to establish ER-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical conditions) that have any one well-behaved curved equality constraint (f(x,y) = 0) are ER-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint (f(x,y) ≥ 0 and g(x,y) ≥ 0) imply ER-completeness on the class of such CCSPs.