Class Description

∃R: Existential theory of the reals

Problems reducible to the language of multivariate polynomials with integer coefficients that have a real solution. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty. Defined in [Sha10].

Contains NP and is contained in PSPACE.

Many problems in discrete and computational geometry are contained in this class.

Linked From

No class.