Continuous optimization problems and a polynomial hierarchy of real functions
From MaRDI portal
Publication:1086557
DOI10.1016/0885-064X(85)90012-3zbMath0609.03015OpenAlexW1993905226MaRDI QIDQ1086557
Publication date: 1985
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0885-064x(85)90012-3
computational complexityminimizationrelativizationmaximizationpolynomial-time computable functionpolynomial-time computable real functionspolynomial-time hierarchy of real functions
Analysis of algorithms and problem complexity (68Q25) Constructive and recursive analysis (03F60) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
On sparse oracles separating feasible complexity classes, A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality, On the complexity of small description and related topics, Degrees and reducibilities of easy tally sets, Kolmogorov complexity and degrees of tally sets, On the complexity of ranking, In Memoriam: Ker-I Ko (1950–2018), Reducibilities on tally and sparse sets, Sets with small generalized Kolmogorov complexity, On the computational complexity of best Chebyshev approximations, All superlinear inverse schemes are coNP-hard
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On self-reducibility and weak P-selectivity
- The computational complexity of maximization and integration
- On some natural complete operators
- The maximum value problem and NP real numbers
- Computational complexity of real functions
- Approximation algorithms for combinatorial problems
- The polynomial-time hierarchy
- A second step toward the polynomial hierarchy
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On the Definition of Computable Function of a Real Variable
