×

On the computational complexity of best Chebyshev approximations. (English) Zbl 0617.03039

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.
Reviewer: G.B.Marandžjan

MSC:

03F60 Constructive and recursive analysis
68Q25 Analysis of algorithms and problem complexity
41A10 Approximation by polynomials
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cheney, E. W., Introduction to Approximation Theory (1982), Chelsea: Chelsea New York · Zbl 0535.41001
[2] Friedman, H., On the computational complexity of maximization and integration, Adv. in Math., 53, 80-98 (1984) · Zbl 0563.03023
[3] Garey, M.; Johnson, D., Computers and Intractability (1979), Freeman: Freeman San Francisco
[4] Goldstein, A. A., A note on the Complexity of an algorithm for Chebyshev approximation, BIT, 24, 503-509 (1984) · Zbl 0559.65008
[5] Hartmanis, J.; Sewelson, V.; Immerman, N., Sparse sets in NP-P: EXPTIME versus NEXPTIME, (Proceedings of 15th ACM Symposium on Theory of Computing (1983)), 382-391 · Zbl 0586.68042
[6] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, Mass. · Zbl 0426.68001
[7] Ko, K., The maximum value problem and NP real numbers, J. Comput. System Sci., 24, 15-35 (1982) · Zbl 0481.03038
[8] Ko, K., On the definitions of some complexity classes of real numbers, Math. Systems Theory, 16, 95-109 (1983) · Zbl 0529.03016
[9] Ko, K., On the computational complexity of ordinary differential equations, Inform. and Control, 58, 157-194 (1983) · Zbl 0541.03035
[10] Ko, K., Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity, 1, 210-231 (1985) · Zbl 0609.03015
[11] Ko, K., Approximation to measurable functions and its relation to probabilistic computation, Ann. Pure Appl. Logic (1986), in press · Zbl 0613.03029
[12] Ko, K.; Friedman, H., Computational complexity of real functions, Theoret. Comput. Sci., 20, 323-352 (1982) · Zbl 0498.03047
[13] Nerode, A.; Huang, W. Q., The application of pure recursion theory to recursive analysis, Acta Math. Sinica, 28, 625-636 (1985), [In Chinese] · Zbl 0638.03058
[14] Pour-el, M. B.; Caldwell, J., On a simple definition of computable functions of a real variable—with applications to functions of a complex variable, Z. Math. Logik Grundlag Math., 23, 1-19 (1975) · Zbl 0323.02049
[15] Rice, J. R., The Approximation of Functions (1964), Addison-Wesley: Addison-Wesley Reading, Mass. · Zbl 0114.27001
[16] Selman, A. L., Reductions on NP and the p-selective sets, Theoret. Comput. Sci., 19, 287-304 (1982) · Zbl 0489.03016
[17] Shepherdson, J. C., On the definition of computable functions of a real variable, Z. Math. Logik Grundlag Math., 22, 301-402 (1976) · Zbl 0359.02029
[18] Specker, E., Der Satz von Maximum in der rekursiven Analysis, (Heyting, A., Constructivity in Mathematics. Constructivity in Mathematics, Studies in Logic and Foundations of Math. (1959), North-Holland: North-Holland Amsterdam), 254-265
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.