An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
From MaRDI portal
Abstract: We prove elementary recursive bounds in the degrees for Positivstellensatz and Hilbert 17-th problem, which is the expression of a nonnegative polynomial as a sum of squares of rational functions. We obtain a tower of five exponentials. A precise bound in terms of the number and degree of the polynomials and their number of variables is provided in the paper.
Recommendations
Cites work
- A new decision method for elementary algebra
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A nullstellensatz for ordered fields
- Algorithms in real algebraic geometry
- Anneaux preordonnes
- Complexity of deciding Tarski algebra
- Complexity of Null- and Positivstellensatz proofs
- Decision procedures for real and p‐adic fields
- Dynamical method in algebra: Effective Nullstellensätze
- Effective Nullstellensatz for arbitrary ideals
- Elementary recursive quantifier elimination based on Thom encoding and sign determination
- Generalizing Cramer's Rule: Solving Uniformly Linear Systems of Equations
- scientific article; zbMATH DE number 3889718 (Why is no real title available?)
- scientific article; zbMATH DE number 3857078 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 3176305 (Why is no real title available?)
- scientific article; zbMATH DE number 16655 (Why is no real title available?)
- scientific article; zbMATH DE number 177492 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 4123858 (Why is no real title available?)
- scientific article; zbMATH DE number 1235881 (Why is no real title available?)
- scientific article; zbMATH DE number 1082910 (Why is no real title available?)
- scientific article; zbMATH DE number 5195 (Why is no real title available?)
- scientific article; zbMATH DE number 939820 (Why is no real title available?)
- scientific article; zbMATH DE number 3238610 (Why is no real title available?)
- scientific article; zbMATH DE number 3309168 (Why is no real title available?)
- scientific article; zbMATH DE number 3335712 (Why is no real title available?)
- scientific article; zbMATH DE number 3381034 (Why is no real title available?)
- scientific article; zbMATH DE number 4185817 (Why is no real title available?)
- scientific article; zbMATH DE number 3058859 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Local Diophantine Nullstellen Inequalities
- Local reality on algebraic varieties
- On the combinatorial and algebraic complexity of quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the effective Nullstellensatz
- Real quantifier elimination is doubly exponential
- Solving systems of polynomial inequalities in subexponential time
- Spécialisation de la suite de Sturm et sous-résultants (I)
- Sums of squares on the hypercube
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- Zero-nonzero and real-nonreal sign determination
Cited in
(16)- On sum of squares certificates of non-negativity on a strip
- On exact Reznick, Hilbert-Artin and Putinar's representations
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- Certifying the global optimality of quartic minimization over the sphere
- Testing hyperbolicity of real polynomials
- On the complexity of testing attainment of the optimal value in nonlinear optimization
- Sums of squares on the hypercube
- scientific article; zbMATH DE number 16655 (Why is no real title available?)
- Geometric theories for the algebra of real numbers
- Artin's theorem for f-rings
- scientific article; zbMATH DE number 7559240 (Why is no real title available?)
- On the effective Putinar's Positivstellensatz and moment approximation
- On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
- Absolute concentration robustness: algebra and geometry
- Lectures on nonnegative polynomials and sums of squares
- Completions to discrete probability distributions in log-linear models
This page was built for publication: An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108709)
