Completeness for the Complexity Class $$\forall \exists \mathbb {R}$$ and Area-Universality
Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Paweł Rzążewski · Discrete & Computational Geometry · 2022
Abstract Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class $$\exists \mathbb {R}$$ ∃ R plays a crucial role in the study of geometric problems. Sometimes $$\exists \mathbb {R}$$ ∃ R is referred to as the ‘real analog’ of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, $$\exists \mathbb {R}$$ ∃ R deals with existentially quantified real variables. In analogy to $$\Pi _2^p$$ Π 2 p and $$\Sigma _2^p$$ Σ 2 p in the famous polynomial hierarchy, we study the complexity classes $$\forall \exists \mathbb {R}$$ ∀ ∃ R and $$ \exists \forall \mathbb {R}$$ ∃ ∀ R with real variables. Our main interest is the AreaUniversality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AreaUniversality is $$\forall \exists \mathbb {R}$$ ∀ ∃ R -complete and support this conjecture by proving $$\exists \mathbb {R}$$ ∃ R - and $$\forall \exists \mathbb {R}$$ ∀ ∃ R -completeness of two variants of AreaUniversality. To this end, we introduce tools to prove $$\forall \exists \mathbb {R}$$ ∀ ∃ R -hardness and membership. Finally, we present geometric problems as candidates for $$\forall \exists \mathbb {R}$$ ∀ ∃ R -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.