On the efficiency of effective Nullstellensätze

DOI10.1007/BF01200407zbMath0824.68051OpenAlexW1979472156MaRDI QIDQ2366723

Marc Giusti, Juan Sabia, Joos Heintz

Publication date: 23 August 1993

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

Full work available at URL: https://doi.org/10.1007/bf01200407

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Nullstellensatz via Nonstandard Methods, Black-box polynomial resultants, On polynomial ideals, their complexity, and applications, Bounds of traces in complete intersections and degrees in the Nullstellensatz, Lower bounds for diophantine approximations, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Elimination of constants from machines over algebraically closed fields, Deformation techniques to solve generalised Pham systems, Straight-line programs in geometric elimination theory, On a tropical dual Nullstellensatz, A concise proof of the Kronecker polynomial system solver from scratch, Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs, Rational invariants of a group action. Construction and rewriting, Tropical effective primary and dual Nullstellensätze, Polynomial bounds for invariant functions separating orbits, A Gröbner free alternative for polynomial system solving, Computing bases of complete intersection rings in Noether position, An algorithm for implicit interpolation, Complexity bounds in elimination theory -- a survey., Multidimensional residues and complexity problems., An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Fast computation of a rational point of a variety over a finite field, Effective equidimensional decomposition of affine varieties

Cites Work

• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• Théoremes de Bertini et applications
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Bounds for the degrees in the Nullstellensatz
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Serre's conjecture
• On the representation of rational functions of bounded complexity
• Berechnung und Programm. I
• Fast Parallel Computation of Polynomials Using Few Processors
• Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
• Ideals of generic minors
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors