Counting Complexity Classes for Numeric Computations I: Semilinear Sets
From MaRDI portal
Publication:4441905
DOI10.1137/S0097539702415950zbMath1069.68049OpenAlexW1971650774WikidataQ57733237 ScholiaQ57733237MaRDI QIDQ4441905
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
Software, source code, etc. for problems pertaining to algebraic topology (55-04) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety, Some Results on Interactive Proofs for Real Computations, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Exotic quantifiers, complexity classes, and complete problems
