Completeness for the Complexity Class $\forall \exists \mathbb{R}$ and Area-Universality

Understand

Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class $\exists \mathbb{R}$ plays a crucial role in the study of geometric problems.

• Sometimes $\exists \mathbb{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}$ deals with existentially quantified real variables.
• In analogy to $\Pi_2^p$ and $\Sigma_2^p$ in the famous polynomial hierarchy, we study the complexity classes $\forall \exists \mathbb{R}$ and $\exists \forall \mathbb{R}$ with real variables.