no. 5
Computer Science/Algebraic Geometry
The complexity to compute the Euler characteristic of complex varieties
[La complexité du calcul de la caractéristique d'Euler des variétés complexes.]

Présenté par : Philippe G. Ciarlet

Bürgisser, Peter1 ; Cucker, Felipe2 ; Lotz, Martin1
1 Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
2 Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong
Comptes Rendus. Mathématique, Tome 339 (2004) no. 5, pp. 371-376.

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 FPR#PR. 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 FPC#PC.

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 FPR#PR. 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 FPC#PC.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.06.008
Bürgisser, Peter 1 ; Cucker, Felipe 2 ; Lotz, Martin 1

1 Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany
2 Department of Mathematics, City University of Hong Kong, 83, Tat Chee Avenue, Kowloon, Hong Kong 
@article{CRMATH_2004__339_5_371_0,
     author = {B\"urgisser, Peter and Cucker, Felipe and Lotz, Martin},
     title = {The complexity to compute the {Euler} characteristic of complex varieties},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {371--376},
     publisher = {Elsevier},
     volume = {339},
     number = {5},
     year = {2004},
     doi = {10.1016/j.crma.2004.06.008},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2004.06.008/}
}
TY  - JOUR
AU  - Bürgisser, Peter
AU  - Cucker, Felipe
AU  - Lotz, Martin
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2004.06.008/
DO  - 10.1016/j.crma.2004.06.008
LA  - en
ID  - CRMATH_2004__339_5_371_0
ER  - 
%0 Journal Article
%A Bürgisser, Peter
%A Cucker, Felipe
%A Lotz, Martin
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2004.06.008/
%R 10.1016/j.crma.2004.06.008
%G en
%F CRMATH_2004__339_5_371_0
Bürgisser, Peter; Cucker, Felipe; Lotz, Martin. The complexity to compute the Euler characteristic of complex varieties. Comptes Rendus. Mathématique, Tome 339 (2004) no. 5, pp. 371-376. doi : 10.1016/j.crma.2004.06.008. http://www.numdam.org/articles/10.1016/j.crma.2004.06.008/

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

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

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

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

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

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

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

[8] Renegar, J. 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] Valiant, L.G. The complexity of computing the permanent, Theoret. Comput. Sci., Volume 8 (1979), pp. 189-201

Cité par Sources :