On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety

DOI10.1016/j.jco.2007.03.008zbMath1127.68038MaRDI QIDQ2371309

Peter Scheiblechner

Publication date: 4 July 2007

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2007.03.008

zbMATH Keywords

connected components; lower bounds; Betti numbers; PSPACE

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

14Q20: Effectivity, complexity and computational aspects of algebraic geometry

Related Items

Effective de Rham cohomology — The general case, A complex analogue of Toda's theorem, On a generalization of Stickelberger's theorem, Computing the homology of real projective sets, On the complexity of counting components of algebraic varieties, Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of semilinear problems in succinct representation
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Polynomial Space Counting Problems
• Filtrations on the homology of algebraic varieties
• Counting Complexity Classes for Numeric Computations I: Semilinear Sets