On the computational complexity of best Chebyshev approximations (Q1821775)

The author defines a formal model of computation of real variable functions (using binary strings to represent real numbers) and investigates a series of problems concerning the best Chebyshev approximations of computable functions on [0,1] from the complexity theory viewpoint. Let \(POLY_ n(R)\) be the set of all polynomials with degree n and rational coefficients and let f be a continuous function on [0,1]. Let \(E_ n(f)\) be defined as follows: \[ E_ n(f)=\min_{\phi \in POLY_ n(R)}\max_{0\leq x\leq 1}| f(x)-\phi (x)|. \] If f is a polynomial-time computable function, then the sequence \(E_ n(f)\) is shown to be NP computable. If \(P=NP\), then for a polynomially computable function f on [0,1] the sequence \(\phi_ n^*\) of the best Chebyshev approximations is polynomial-time computable. A series of other theorems of such kind are proved. The paper contains a series of open problems.