∀∃ℝ-Completeness and Area-Universality

Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski

Abstract

In the study of geometric problems, the complexity class $$\exists \mathbb {R}$$ plays a crucial role since it exhibits a deep connection between purely geometric problems and real algebra. Sometimes $$\exists \mathbb {R}$$ is referred to as the “real analogue” to the class NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, $$\exists \mathbb {R}$$ deals with existentially quantified real variables. In analogy to $$\varPi _2^p$$ and $$\varSigma _2^p$$ in the famous polynomial hierarchy, we study the complexity classes $$\forall \exists \mathbb {R}$$ and $$\exists \forall \mathbb {R}$$ with real variables. Our main interest is focused on the Area Universality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G there is an area-realizing straight-line drawing of G. We conjecture that the problem Area Universality is $$\forall \exists \mathbb {R}$$ -complete and support this conjecture by a series of partial results, where we prove $$\exists \mathbb {R}$$ - and $$\forall \exists \mathbb {R}$$ -completeness of variants of Area Universality. To do so, we also introduce first tools to study $$\forall \exists \mathbb {R}$$ . Finally, we present geometric problems as candidates for $$\forall \exists \mathbb {R}$$ -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.
BibTeX
@inproceedings{dobbins2018r,
  author = {Michael Gene Dobbins and Linda Kleist and Tillmann Miltzow and Pawel Rzazewski},
  title = {{∀∃ℝ-Completeness and Area-Universality}},
  booktitle = {WG},
  year = {2018},
  doi = {10.1007/978-3-030-00256-5\_14},
}

Loading related content...

Figure