Beyond the Existential Theory of the Reals
From MaRDI portal
Publication:6489317
DOI10.1007/S00224-023-10151-XMaRDI QIDQ6489317
Daniel Štefanković, Marcus Schaefer
Publication date: 21 April 2024
Published in: Theory of Computing Systems (Search for Journal in Brave)
Semialgebraic sets and related spaces (14P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Read-once polynomial identity testing
- Fixed points, Nash equilibria, and the existential theory of the reals
- Exotic quantifiers, complexity classes, and complete problems
- Real addition and the polynomial hierarchy
- Some provably hard crossing number problems
- Effective Łojasiewicz inequalities in semialgebraic geometry
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Intersection graphs of segments
- An exact duality theory for semidefinite programming and its complexity implications
- \(\forall\exists\mathbb {R}\)-completeness and area-universality
- Generalizations of matched CNF formulas
- Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
- The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
- Computational complexity of multi-player evolutionarily stable strategies
- On the minimum of a positive polynomial over the standard simplex
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Realizability of Graphs and Linkages
- On the Complexity of Numerical Analysis
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- The Art Gallery Problem is ∃ℝ-complete
- Smoothing the Gap Between NP and ER
- Computing the real isolated points of an algebraic hypersurface
- Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
- Semidefinite programming and combinatorial optimization
- On the computational complexity of decision problems about multi-player Nash equilibria
- Algorithms in real algebraic geometry
- The Complexity of Angular Resolution
- The complexity of the Hausdorff distance
- Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
This page was built for publication: Beyond the Existential Theory of the Reals
