Continuous optimization problems and a polynomial hierarchy of real functions (Q1086557): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0885-064x(85)90012-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1993905226 / rank | |||
Normal rank |
Latest revision as of 10:17, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Continuous optimization problems and a polynomial hierarchy of real functions |
scientific article |
Statements
Continuous optimization problems and a polynomial hierarchy of real functions (English)
0 references
1985
0 references
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.
0 references
polynomial-time computable function
0 references
computational complexity
0 references
maximization
0 references
minimization
0 references
polynomial-time computable real functions
0 references
polynomial-time hierarchy of real functions
0 references
relativization
0 references