On the Complexity of Counting Irreducible Components and Computing Betti Numbers of Algebraic Varieties
Peter Scheiblechner · Amtliche Mitteilungen (Universitätsbibliothek Paderborn) · 2007
This thesis is a continuation of the study of counting problems in algebraic geometry within an algebraic framework of computation started by Bürgisser, Cucker, and Lotz in a series of papers [BC03,BC06,BCL05].In its first part we give a uniform method for the two problems #CC C and #IC C of counting the connected and irreducible components of complex algebraic varieties, respectively.Our algorithms are purely algebraic, i.e., they use only the field structure of C. They work in parallel polynomial time, i.e., they can be implemented by algebraic circuits of polynomial depth.The design of our algorithms relies on the concept of algebraic differential forms.A further important building block is an algorithm of Szántó [Szá97] computing a variant of characteristic sets.The second part contains lower bounds in terms of hardness results for topological problems dealing with complex algebraic varieties.In particular, we show that the problem of deciding connectedness of a complex affine or projective variety given over the rationals is PSPACE-hard.We further extend this result to higher Betti numbers.More precisely, we prove that it is also PSPACE-hard to decide whether a Betti number of fixed order of a complex affine or projective variety is less than some given integer.In the third part we study the dependency of the complexity of #IC C on its combinatorial parameters.The crucial complexity parameter for the problem turns out to be the number of equations.This fact is illustrated by our result about counting the absolutely irreducible factors of a multivariate polynomial, the restriction of the general problem to the case of a single equation.We show that one can solve this problem in parallel polylogarithmic time.Furthermore, we describe a generic parsimonious reduction of the problem #IC C for a fixed number of equations to a fixed number of variables.The consequences are that one can solve #IC C for a fixed number of equations in the BSS-model in polynomial time, and in the Turing model in randomised parallel polylogarithmic time.These results hold also for polynomials given by straight-line programs using their length and the degree as input parameters.v vi Danksagungen Mein allergrößter Dank gilt meinem Doktorvater Peter Bürgisser für sein Vertrauen und dafür, dass er mir die Möglichkeit der Promotion gegeben hat, seine sehr gute und immer freundliche Betreuung und Unterstützung in vielerlei Hinsicht, und alles, was ich von ihm (auch außermathematisch) gelernt habe.Weiterhin herzlich bedanken möchte ich mich bei Thilo Pruschke für das Finden eines Fehlers und hilfreiche Diskussionen über das Hilbertpolynom.Außerdem haben mir meine Arbeitsgruppenkollegen Martin Lotz und Martin Ziegler mit einer angenehmen Arbeitsatmosphäre und vielen wertvollen Gesprächen geholfen.Nicht zuletzt bedanke ich mich ganz herzlich bei meiner Familie