Completeness for the Complexity Class ∀ ∃ R and Area-Universality.

Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃ R plays a crucial role in the study of geometric problems. Sometimes ∃ 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, ∃ R deals with existentially quantified real variables. In analogy to Π 2 p and Σ 2 p in the famous polynomial hierarchy, we study the complexity classes ∀ ∃ R and ∃ ∀ R with real variables. Our main interest is 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 exists a straight-line drawing of G realizing the assigned areas. We conjecture that Area Universality is ∀ ∃ R -complete and support this conjecture by proving ∃ R - and ∀ ∃ R -completeness of two variants of Area Universality. To this end, we introduce tools to prove ∀ ∃ R -hardness and membership. Finally, we present geometric problems as candidates for ∀ ∃ R -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.