REVIEW 5 cited by
The Existential Theory of the Reals as a Complexity Class: A Compendium
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We survey the complexity class $\exists \mathbb{R}$, which captures the complexity of deciding the existential theory of the reals. The class $\exists \mathbb{R}$ has roots in two different traditions, one based on the Blum-Shub-Smale model of real computation, and the other following work by Mn\"{e}v and Shor on the universality of realization spaces of oriented matroids. Over the years the number of problems for which $\exists \mathbb{R}$ rather than NP has turned out to be the proper way of measuring their complexity has grown, particularly in the fields of computational geometry, graph drawing, game theory, and some areas in logic and algebra. $\exists \mathbb{R}$ has also started appearing in the context of machine learning, Markov decision processes, and probabilistic reasoning. We have aimed at collecting a comprehensive compendium of problems complete and hard for $\exists \mathbb{R}$, as well as a long list of open problems. The compendium is presented in the third part of our survey; a tour through the compendium and the areas it touches on makes up the second part. The first part introduces the reader to the existential theory of the reals as a complexity class, discussing its history, motivation and prospects as well as some technical aspects.
Forward citations
Cited by 5 Pith papers
-
Algorithms for Equilibria in Concurrent Stopping Games
Approximate constrained NE existence in concurrent stopping games is EXPTIME (PSPACE-hard); XRSE constrained existence is NP-complete.
-
Point Set Embeddability with List Constraints
List-constrained point-set embeddability is poly-time or FPT for connected graphs on convex points, but NP-hard already for bi-labeled matchings (convex) and bi-labeled paths (general), with matching FPT/paraNP dichot...
-
Toward Satisfiability Modulo Realizability
The largest set of points in the plane with no empty convex hexagon and no convex heptagon has size 23, proved by a SAT-modulo-realizability solver that finds thousands of witnessing configurations.
-
Data-Efficient Safe Policy Improvement Using Parametric Structure
Parametric SPIBB and game-based pruning reduce the data required for safe policy improvement by up to two orders of magnitude, while SMT-based pruning is shown to be computationally infeasible.
-
Some structural complexity results for $\exists\mathbb R$
This paper proves oracle, logical, and Ladner-type structural theorems for the complexity class ∃R, some conditional on ∃R being different from NP.
Discussion (0). Continue with ORCID to comment.