Counting Complexity Classes for Numeric Computations I: Semilinear Sets

DOI10.1137/S0097539702415950MaRDI QIDQ4441905zbMATH OpenOpenAlexWikidataFDO

Authors Peter Bürgisser, Felipe Cucker

Publication date 8 January 2004

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539702415950

zbMATH Keywords

Betti numberscounting complexityEuler characteristicreal complexity classes

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to algebraic topology (55-04) Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algorithms and Computation
• Counting complexity classes for numeric computations II
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Counting complexity classes for numeric computations. III: Complex projective sets
• scientific article; zbMATH DE number 1361497

Cited in

(8)

• Exotic quantifiers, complexity classes, and complete problems
• On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Counting complexity classes for numeric computations. III: Complex projective sets
• Semilinear sets and counter machines: a brief survey
• Some results on interactive proofs for real computations
• Counting complexity classes for numeric computations II
• Algorithms and Computation

This page was built for publication: Counting Complexity Classes for Numeric Computations I: Semilinear Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4441905)