Probabilistically checkable proofs for the Existential Theory of the Reals

Jack Stade

We prove a PCP theorem for the existential theory of the reals, showing that MAX-ETR-INV is $\exists \mathbb{R}$-hard to approximate to within some constant factor. The existential…