Computational complexity of fragments of the theory of complex numbers

Abstract

We discuss the computational complexity of formulas in prenex form with bounded quantifier alternation depth. In particular, we have to do with the theory of algebraically closed fields. It is proved that recognition of multidimensional cube vertices on the hyperplane can be reduced to recognition of singular points on a hypersurface constructed in polynomial time. Moreover, some relations between complexity classes are proved. Finally, we discuss how one can improve a concept of complexity as well as connection with the model theory.