Real Algebraic and Analytic Geometry Preprint Server

e-mail:
homepage: http://www.math.uni-konstanz.de/~scheider/index.html

Submission: 2004, August 28.

Abstract:
Given polynomials h_1,...,h_r in R[x_1,...,x_n], we study the complexity of the problem of representing polynomials in the form f = s_0+s_1h_1+\cdots+s_rh_r (*) with sums of squares s_i. Let M be the cone of all f which admit such a representation. The problem is said to be stable if there exists a function phi: N --> N such that every f in M has a representation (*) with \deg(s_i) <= phi(deg(f)). The main result says that if the set K = {h_1>=0,...,h_r>=0} has dimension $>=2$ and the sequence h_1,...,h_r has the moment property (MP), then the problem is not stable. In particular, this includes the case when K is compact, dim(K) >= 2 and the cone M is multiplicatively closed .

Mathematics Subject Classification (2000): 14P05, 14P10, 26D05, 44A60, 68Q17.

Keywords and Phrases: Non-negative polynomials, sums of squares, complexity, moment problem, real algebraic geometry.

Full text, 16p.: dvi 91k, ps.gz 190k, pdf 296k.