Beyond the Existential Theory of the Reals

We show that completeness at higher levels of the theory of the reals is a robust notion (under changing the signature and bounding the domain of the quantifiers). This mends recognized gaps in the hierarchy, and leads to stronger completeness results for various computational problems. We exhibit several families of complete problems which can be used for future completeness results in the real hierarchy. As an application we answer an open question by Jungeblut, Kleist, and Miltzow on the complexity of two semialgebraic sets having Hausdorff distance $0$, and sharpen some results by Burgisser and Cucker.