TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Page Content

to Navigation

There is no English translation for this web page.

Journal Publications

Counting Complexity Classes for Numeric Computations III: Complex Projective Sets
Citation key BCL-Counting-Complexity-Classes-For-Numeric-Computations-Iii-Complex-Projective-Sets
Author Peter Bürgisser and Felipe Cucker and Martin Lotz
Pages 351-387
Year 2005
Journal Foundations of Computational Mathematics
Volume 5
Number 4
Abstract In [Bürgisser & Cucker 2004a] counting complexity classes $\#P_R$ and $\#P_C$ in the Blum-Shub-Smale setting of computations over the real and complex numbers, respectively, were introduced. One of the main results of [Bürgisser & Cucker 2004a] is that the problem to compute the Euler characteristic of a semialgebraic set is complete in the class $FP_R^R}$. In this paper, we prove that the corresponding result is true over $\mathbb C$, namely that the computation of the Euler characteristic of an affine or projective complex variety is complete in the class $FP_C^C}$. We also obtain a corresponding completeness result for the Turing model.
Link to publication Link to original publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe