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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q1295380
Set OpenAlex properties.
 
(3 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Ker-I. Ko / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question / rank
 
Normal rank
Property / cites work
 
Property / cites work: A second step toward the polynomial hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: The computational complexity of maximization and integration / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3862379 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximation algorithms for combinatorial problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: The maximum value problem and NP real numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: On self-reducibility and weak P-selectivity / rank
 
Normal rank
Property / cites work
 
Property / cites work: On some natural complete operators / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computational complexity of real functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Definition of Computable Function of a Real Variable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3260574 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The polynomial-time hierarchy / rank
 
Normal rank
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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references