A PSPACE construction of a hitting set for the closure of small algebraic circuits
A PSPACE construction of a hitting set for the closure of small algebraic circuits
In this paper we study the complexity of constructing a hitting set for VP, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given …