On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety |
| |
Authors: | Peter Scheiblechner |
| |
Institution: | Department of Mathematics, University of Paderborn, D-33095 Paderborn, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Connected components Betti numbers PSPACE Lower bounds |
本文献已被 ScienceDirect 等数据库收录! |
|