Complexity theory aims at the understanding of the inherent hardness of computational problems. This book studies the complexity of the most basic counting problems in algebraic geometry within an algebraic framework of computation. The author gives an efficient parallel method for the two problems of counting the connected and irreducible components of complex algebraic varieties. On the other hand, it is shown that deciding connectedness of varieties is PSPACE-hard. This result is also extend to higher Betti numbers. Furthermore, the problem of counting irreducible components for a fixed number of equations is reduced to a fixed number of variables. The consequences are a polynomial time algorithm in the BSS-model, and a randomised parallel polylogarithmic time algolrithm in the Turing model. The book is intended for mathematicians interested in computational complexity, and for computer scientists interested in algebraic geometry. The required prerequisites are completely presented, so the text should be accessable to graduate students.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.