Complexity of Counting Components of Algebraic Varieties - Irreducible and Connected Components, Betti Numbers
Cód:
491_9783836498449
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.
Veja mais
