On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety

We extend the lower bounds on the complexity of computing Betti numbers proved in [P. Bürgisser, F. Cucker, Counting complexity classes for numeric computations II: algebraic and semialgebraic sets, J. Complexity 22 (2006) 147–191] to complex algebraic varieties. More precisely, we first prove that the problem of deciding connectedness of a complex affine or projective variety given as the zero set of integer polynomials is PSPACE-hard. Then we prove PSPACE-hardness for the more general problem of deciding whether the Betti number of fixed order of a complex affine or projective variety is at most some given integer.