Some speed-ups and speed limits for real algebraic geometry

DOI10.1006/jcom.2000.0553zbMath1008.14012arXivmath/9905004OpenAlexW2156324599MaRDI QIDQ1594829

J. Maurice Rojas

Publication date: 6 April 2003

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

Full work available at URL: https://arxiv.org/abs/math/9905004

zbMATH Keywords

fewnomialcomplexity classnumber of connected components of a semialgebraic set

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Deformation techniques to solve generalised Pham systems ⋮ On solving univariate sparse polynomials in logarithmic time ⋮ The real linear eigenvalue problem in \(\mathbb C^n\) ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ Factoring matrices into the product of circulant and diagonal matrices ⋮ Betti number bounds for fewnomial hypersurfaces via stratified Morse theory

Uses Software

• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Bounding the number of connected components of a real algebraic set
• On the complexity of computations under varying sets of primitives
• A polynomial time algorithm for diophantine equations in one variable
• Combining binary search and Newton's method to compute real roots for a class of real functions
• Solving degenerate sparse polynomial systems faster
• Algebraic Geometry. I: Complex projective varieties.
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
• An efficient algorithm for the complex roots problem
• On the complexity of diophantine geometry in low dimensions (extended abstract)
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
• NEWTON POLYHEDRA AND AN ALGORITHM FOR COMPUTING HODGE–DELIGNE NUMBERS
• Lower bounds for algebraic decision trees
• On the combinatorial and algebraic complexity of quantifier elimination
• On The Complexity of Computing Mixed Volumes
• Asymptotic acceleration of solving multivariate polynomial systems of equations
• On the Betti Numbers of Real Varieties
• A Gröbner free alternative for polynomial system solving

This page was built for publication: Some speed-ups and speed limits for real algebraic geometry