Real Algebraic and Analytic Geometry |

Moment problem and complexity.

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.

Server Home Page