Functions and Analysis

Finding the Maximum of a Polynomial Time Computable Bounded Smooth Function on an Interval is NP-Complete

Authors: Warren D. Smith
Comments: 3 Pages.

Ker-I Ko in his 1991 book "Complexity theory of real functions" (Birkhauser) defined the notions of polynomial-time computable (P.T.C.) real numbers and real functions. On p.106 he posed as an open question "whether differentiability helps in computing maximum values." We argue the answer is "no."

But in order to make this argument, Ko's theory needs to be extended to encompass notions of the codelength of a P.T.C. real number, and the code transformation time for various real arithmetic operations. The question in Ko's unextended theory remains unsolved.

Our result is: If F(x) is C and bounded and P.T.C. on [0,1], then the maximum M of F on [0,1] either

1. is not P.T.C.,
2. or if it is, then the code of M is not produceable by a polytime algorithm from the code for F, or
3. P=NP.

Category: Functions and Analysis