One thing that's not always apparent when thinking about traditional "continuous m...

One thing that's not always apparent when thinking about traditional "continuous math" problems is the way discrete, combinatorial issues

of the kind we re studying here can creep into what look like standard calculus questions.

Consider, for example, the traditional problem of minimizing a one-variable function like f(x) = 3 + x – 3x2 over an interval like x ε [0,1]. The derivative has a zero at x = 1/6, but this in fact is a maximum of the function, not a minimum; to get the minimum, one has to heed the standard warning to check the values on the boundary of the interval as well. (The minimum is in fact achieved on the boundary, at x = 1.)

Checking the boundary isn't such a problem when you have a function in one variable; but suppose we re now dealing with the problem of minimizing a function in n variables x1, x2, ...,xn over the unit cube, where each of x1, x2 , ... , xn ε [0, 1]. The minimum may be achieved on the interior of the cube, but it may be achieved on the boundary; and this latter prospect is rather daunting, since the boundary consists of 2n "corners" (where each xi is equal to either 0 or 1) as well as various pieces of other dimensions. Calculus books tend to get suspiciously vague around here, when trying to describe how to handle multivariable minimization problems in the face of this complexity.

It turns out there's a reason for this: Minimizing an n-variable function over the unit cube in n dimensions is as hard as an NP-complete problem. To make this concrete, let s consider the special case of polynomials with integer coefficients over n variables x1, x2,... , xn. To review some terminology, we say a monomial is a product of a real-number coefficient c and each variable xi raised to some nonnegative integer power ai; we can write this as cx< a1x2!2 - ... (For example, 2x2x2x is a monomial.) A polynomial is then a sum of a finite set of monomials. (For example, 2x\x2x3 + x1x3 –- 6x2 x2 is a polynomial.)

We define the Multivariable Polynomial Minimization Problem as follows: Given a polynomial in n variables with integer coefficients, and given an integer bound B, is there a choice of real numbers x1, x2,xn ε [0,1] that causes the polynomial to achieve a value that is

Choose a problem Y from this chapter that is known to be NP-complete and show that

Y ≤P Multivariable Polynomial Minimization.