Continuous optimization problems and a polynomial hierarchy of real functions (Q1086557): Difference between revisions

Let f on \([0,1]^ 2\) be a polynomial-time computable function in the sense that for any given rational number r, an approximation s to f(r), with an error bounded by \(2^{-n}\), can be found in time polynomial in n. What can we say about the computational complexity of the function \(\max_ f\) defined by \(\max_ f(x)=\max_{y\in [0,1]}f(x,y)?\) The author [J. Comput. Syst. Sci. 24, 15-35 (1982; Zbl 0481.03038)] and \textit{H. Friedman} [Adv. Math. 53, 80-98 (1984; Zbl 0563.03023)] showed that the function \(\max_ f\) is polynomial-time computable for all polynomial-time computable f if and only if \(P=NP\). This paper extends this result to the alternating operations of maximization and minimization on polynomial-time computable real functions. First, the notion of the polynomial-time hierarchy of real functions is established as the continuous analogue of the Meyer-Stockmeyer polynomial-time hierarchy. Then it is proved that the functions defined by k alternating max/min operations on polynomial-time computable real functions are exactly those in the kth level of the polynomial-time hierarchy of real functions; furthermore, this hierarchy collapses if and only if the Meyer-Stockmeyer polynomial-time hierarchy collapses. Also discussed are some connections between the structure of real functions and the notion of relativization.