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 onevariable function like f(x) = 3 + x − 3x² 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 x₁, x₂,..., x_n over the unit cube, where each of x₁, x₂,..., x_n ∈ [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 2ⁿ “corners” (where each x_i 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 x₁, x₂,..., x_n. 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  . (For example,  is a monomial.) A polynomial is then a sum of a finite set of monomials. (For example, 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 x₁, x₂,..., x_n ∈ [0, 1] that causes the polynomial to achieve a value that is ≤ B?

Choose a problem Y from this chapter that is known to be NPcomplete and show that

Y ≤_P Multivariable Polynomial Minimization.