The maximum value problem and NP real numbers

DOI10.1016/0022-0000(82)90053-8zbMath0481.03038OpenAlexW2004966370MaRDI QIDQ1161742

Ker-I. Ko

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90053-8

zbMATH Keywords

maximum value of a continuous polynomial time computable real functionNP computable real numberNP sets over a single-letter alphabet

Mathematics Subject Classification ID

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

Continuous optimization problems and a polynomial hierarchy of real functions, Approximation to measurable functions and its relation to probabilistic computation, Computing power series in polynomial time, On the computational complexity of the Dirichlet Problem for Poisson's Equation, Computational complexity of real functions, In Memoriam: Ker-I Ko (1950–2018), The Power of Self-Reducibility: Selectivity, Information, and Approximation, ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy, On the definitions of some complexity classes of real numbers, Analytical properties of resource-bounded real functionals, On the computational complexity of best Chebyshev approximations, On self-reducibility and weak P-selectivity, Reducibilities on real numbers, The computational complexity of maximization and integration

Cites Work

• Computational complexity of real functions
• The polynomial-time hierarchy
• On the definitions of some complexity classes of real numbers
• On the Structure of Polynomial Time Reducibility
• Toward Abstract Numerical Analysis
• Nicht konstruktiv beweisbare Sätze der Analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item