Xref: utzoo sci.math:10148 comp.theory:413
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!pasteur!helios.ee.lbl.gov!ucsd!ucrmath!marek
From: marek@ucrmath
Newsgroups: sci.math,comp.theory
Subject: polynomials
Message-ID: <4499@ucrmath.UCR.EDU>
Date: 4 Mar 90 23:00:59 GMT
Sender: news@ucrmath.UCR.EDU
Reply-To: marek@ucrmath ()
Organization: University of California, Riverside
Lines: 35

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
-----------------------------------------------------------------------