On the computational complexity of best Chebyshev approximations

DOI10.1016/0885-064X(86)90014-2zbMath0617.03039OpenAlexW2018772645MaRDI QIDQ1821775

Ker-I. Ko

Publication date: 1986

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(86)90014-2

zbMATH Keywords

polynomially computable functionbest Chebyshev approximations of computable functionsformal model of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Constructive and recursive analysis (03F60) Approximation by polynomials (41A10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (4)

Proof mining in \(L_{1}\)-approximation ⋮ New effective moduli of uniqueness and uniform a priori estimates for constants of strong unicity by logical analysis of known proofs in best approximation theory ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Effective moduli from ineffective uniqueness proofs. An unwinding of de La Vallée Poussin's proof for Chebycheff approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The computational complexity of maximization and integration
• Continuous optimization problems and a polynomial hierarchy of real functions
• Approximation to measurable functions and its relation to probabilistic computation
• The maximum value problem and NP real numbers
• Reductions on NP and p-selective sets
• Computational complexity of real functions
• A note on the complexity of an algorithm for Chebyshev approximation
• On the definitions of some complexity classes of real numbers
• On the computational complexity of ordinary differential equations
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• On a simple definition of computable function of a real variable‐with applications to functions of a complex variable
• On the Definition of Computable Function of a Real Variable

This page was built for publication: On the computational complexity of best Chebyshev approximations