Smoothing the gap between NP and ER

Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow

We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if i…