marek@ucrmath (03/05/90)
We have a problem that looks pretty classic, but we don't know the
solution.
You are given a polynomial with integer coefficients over n variables,
p(x_1,... x_n). You want to know whether the polynomial is always
non-negative for non-negative values of x_i (real values).
Example 1
p(x,y,z) = 2x^3 - x^2y + 2xy^2 + yz^2 - xyz
Answer: Yes, because it is = 2x(x^2 - xy + y^2) + y(z^2 - xz + x^2).
Example 3
p(x,y) = x^2 - 3xy + y^2
Answer: No. (Counter example: (1,1))
In our application, all polynomials are homogeneous.
Question: what is known about the time complexity of this problem?
So far, we've been lucky, and all polynomials we've gotten have had all
non-negative coefficients, which makes the problem trivial, or we can make
a transformation to make that true. It may get worse as we go up.
Marek Chrobak & Larry Larmore
-----------------------------------------------------------------------
Marek Chrobak email: marek@ucrmath.ucr.edu
Math & CS, UC Riverside phone: (714) 787-3769
-----------------------------------------------------------------------dgc@vijayaraghavan.math.ucla.edu (David G. Cantor) (03/06/90)
In article <4499@ucrmath.UCR.EDU> marek@ucrmath () writes: We have a
problem that looks pretty classic, but we don't know the solution.
You are given a polynomial with integer coefficients over
n variables, p(x_1,... x_n). You want to know whether the
polynomial is always non-negative for non-negative values of x_i
(real values).
------------------------------------------------------------------------
This is closely related to Hilbert Problem 17, solved by Emil Artin. He
showed that a polynomial with real coefficients is non-negative for all
real values of its variables if and only if it is a sum of squares of
rational functions (not necessarily polynomials) in the same variables.
Theodore Motzkin gave a simple example of such a polynomial which is not
a sum of squares of polynomials.
For the case here, where the variables are are to be non-negative, then
it follows from Artin's reasoning that a polynomial is non-negative
if and only if it is a sum of squares of rational functions, each one
possibly multiplied by one or more of the (non-negative) variables.
For a "logical" proof, see Abraham Robinson's book on Model Theory.
Constructive methods are available. In particular, Tarski published a
decision procedure for the real numbers which handles this problem. The
complexity is quite large however.
In the above any real-closed field can be substituted for the field
of real numbers.
dgc
David G. Cantor
Department of Mathematics
University of California at Los Angeles
Internet: dgc@math.ucla.edu
UUCP: ...!{randvax, sdcrdcf, ucbvax}!ucla-cs!dgcvicki@mathcs.emory.edu (Vicki Powers) (03/06/90)
In article <2335@sunset.MATH.UCLA.EDU>, dgc@vijayaraghavan.math.ucla.edu (David G. Cantor) writes: > This is closely related to Hilbert Problem 17, solved by Emil Artin. He > showed that a polynomial with real coefficients is non-negative for all Correction: Hilbert's 17th problem was solved by Artin and Schreier. They developed the theory of ordered fields to do so. Vicki -- Vicki Powers | vicki@mathcs.emory.edu PREFERRED Emory University | {sun!sunatl,gatech}!emory!vicki UUCP Dept of Math and CS | vicki@emory NON-DOMAIN BITNET Atlanta, GA 30322 |