Real Algebraic and Analytic Geometry |
![]() |
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.