The existential theory of the reals (ETR) consists of existentially quantified boolean formulas over equalities and inequalities of real-valued polynomials. We propose the approximate existential theory of the reals (\epsilon-ETR), in which the constraints only need to be satisfied approximately. We first show that unconstrained \epsilon-ETR = ETR  , and then study the  \epsilon-ETR problem when the solution is constrained to lie in a given  convex set. Our main theorem is a sampling theorem, similar to those that have been proved for approximate equilibria in normal form games. It states that if an ETR problem has an exact solution, then it has a k-uniform approximate solution, where k depends on various properties of the formula. A consequence of our theorem is that we obtain a quasi-polynomial time approximation scheme (QPTAS) for a fragment of constrained \epsilon-ETR. We use our theorem to create several new PTAS and QPTAS algorithms for problems from a variety of fields.
The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of variables in \mathbb{R the approximate existential theory of the reals (\epsilon-ETR), in which the constraints only need to be satisfied approximately. We first show that when the domain of the variables is \mathbb{R \epsilon-ETR = ETR under polynomial time reductions , and then study the constrained \epsilon-ETR problem when the variables are constrained to lie in a given bounded convex set. Our main theorem is a sampling theorem, similar to those that have been proved for approximate equilibria in normal form games. It discretizes the domain in a grid-like manner whose density depends on various properties of the formula. A consequence of our theorem is that we obtain a quasi-polynomial time approximation scheme (QPTAS) for a fragment of constrained \epsilon-ETR. We use our theorem to create several new PTAS and QPTAS algorithms for problems from a variety of fields.
R
existential theory of the reals
Existential Theory of the Reals
R
boolean
Boolean
R
real-valued polynomials. We propose
polynomial functions of variables in \mathbb{R
R
unconstrained
when the domain of the variables is \mathbb{R
A
under polynomial time reductions
A
constrained
R
solution is
variables are
A
bounded
R
states that if an ETR problem has an exact solution, then it has a k-uniform approximate solution, where k
discretizes the domain in a grid-like manner whose density