Comptes Rendus
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

Peter Bürgisser1 ; Felipe Cucker2 ; Martin Lotz1
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, Volume 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
Peter Bürgisser 1 ; Felipe Cucker 2 ; Martin Lotz 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 = {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},
     publisher = {Elsevier},
     volume = {339},
     number = {5},
     year = {2004},
     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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.06.008/

[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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

General formulas for the smoothed analysis of condition numbers

Peter Bürgisser; Felipe Cucker; Martin Lotz

C. R. Math (2006)