An elementary recursive bound for effective Positivstellensatz and Hilbert 17-th problem

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.

References in corpus (1)

• Sums of Squares on the Hypercube

Cited by in corpus (7)

• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• SOS-Convex Lyapunov Functions and Stability of Difference Inclusions
• Sums of Squares: A Real Projective Story
• Elementary recursive quantifier elimination based on Thom encoding and sign determination
• On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization
• Complexity Aspects of Fundamental Questions in Polynomial Optimization
• An efficient sum of squares nonnegativity certificate for quaternary quartic