The complexity to compute the Euler characteristic of complex varieties

Peter Bürgisser; Felipe Cucker; Martin Lotz

doi:10.1016/j.crma.2004.06.008

Computer Science/Algebraic Geometry

The complexity to compute the Euler characteristic of complex varieties

Presented by: Philippe G. Ciarlet

Peter Bürgisser ¹ ; Felipe Cucker ² ; Martin Lotz ¹

¹ Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
² Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong

Comptes Rendus. Mathématique, Volume 339 (2004) no. 5, pp. 371-376

Abstract (Original language)
Résumé

We extend one of the main results of Bürgisser and Cucker (http://www.arxiv.org/abs/cs/cs.CC/0312007), which asserts that the computation of the Euler characteristic of a semialgebraic set is complete in the counting complexity class ${FP}_{R}^{# P_{R}}$ . The goal is to prove a similar result over $C$ : the computation of the Euler characteristic of an affine or projective complex variety is complete in the class ${FP}_{C}^{# P_{C}}$ .

Dans cette Note, nous étendons un des résultats principaux de Bürgisser et Cucker (http://www.arxiv.org/abs/cs/cs.CC/0312007), qui établit que le calcul de la caractéristique d'Euler d'un ensemble semialgébrique est complet dans la classe de complexité de comptage ${FP}_{R}^{# P_{R}}$ . Nous prouvons un résultat similaire sur $C$ : le calcul de la caractéristique d'Euler d'une variété algébrique (affine ou projective) est complet dans la classe ${FP}_{C}^{# P_{C}}$ .

Received: 2004-06-07
Accepted: 2004-06-14
Published online: 2004-07-28

DOI: 10.1016/j.crma.2004.06.008

Author's affiliations:

Peter Bürgisser ¹ ; Felipe Cucker ² ; Martin Lotz ¹

¹ Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
² Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong

@article{CRMATH_2004__339_5_371_0,
     author = {Peter B\"urgisser and Felipe Cucker and Martin Lotz},
     title = {The complexity to compute the {Euler} characteristic of complex varieties},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {371--376},
     year = {2004},
     publisher = {Elsevier},
     volume = {339},
     number = {5},
     doi = {10.1016/j.crma.2004.06.008},
     language = {en},
}

TY  - JOUR
AU  - Peter Bürgisser
AU  - Felipe Cucker
AU  - Martin Lotz
TI  - The complexity to compute the Euler characteristic of complex varieties
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 371
EP  - 376
VL  - 339
IS  - 5
PB  - Elsevier
DO  - 10.1016/j.crma.2004.06.008
LA  - en
ID  - CRMATH_2004__339_5_371_0
ER  -

%0 Journal Article
%A Peter Bürgisser
%A Felipe Cucker
%A Martin Lotz
%T The complexity to compute the Euler characteristic of complex varieties
%J Comptes Rendus. Mathématique
%D 2004
%P 371-376
%V 339
%N 5
%I Elsevier
%R 10.1016/j.crma.2004.06.008
%G en
%F CRMATH_2004__339_5_371_0

Peter Bürgisser; Felipe Cucker; Martin Lotz. The complexity to compute the Euler characteristic of complex varieties. Comptes Rendus. Mathématique, Volume 339 (2004) no. 5, pp. 371-376. doi: 10.1016/j.crma.2004.06.008

References
Cited by

[1] P. Aluffi Computing characteristic classes of projective schemes, J. Symbolic Comput., Volume 35 (2003) no. 1, pp. 3-19

[2] L. Blum; F. Cucker; M. Shub; S. Smale Complexity and Real Computation, Springer-Verlag, New York, 1998

[3] P. Bürgisser; F. Cucker Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets, Proc. 36th Ann. ACM STOC, 2004 (Full version in) | arXiv

[4] P. Bürgisser; F. Cucker; M. Lotz Counting complexity classes for numeric computations III: Complex projective sets, 2004 http://math-www.upb.de/agpb (Full version in in preparation)

[5] A. Dimca Singularities and Topology of Hypersurfaces, Universitext, Springer-Verlag, 1992

[6] J. Harris Algebraic Geometry, Graduate Texts in Math., vol. 133, Springer-Verlag, New York, 1995

[7] P. Koiran Randomized and deterministic algorithms for the dimension of algebraic varieties, Proc. 38th FOCS, 1997, pp. 36-45

[8] J. Renegar On the computational complexity and geometry of the first-order theory of the reals. Part I, II, III, J. Symbolic Comput., Volume 13 (1992) no. 3, pp. 255-352

[9] L.G. Valiant The complexity of computing the permanent, Theoret. Comput. Sci., Volume 8 (1979), pp. 189-201

Cited by Sources:

Comments - Policy