Skip to main content
SpringerLink
Log in

Complexity of approximation problems

  • Published:
Ukrainian Mathematical Journal Aims and scope

Abstract

We consider some aspects of optimal encoding and renewal related to the problem of complexity of the ε-definition of functions posed by Kolmogorov in 1962. We present some estimates for the ε-complexity of the problem of renewal of functions in the uniform metric and Hausdorff metric.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Kolmogorov, “Different approaches to the estimation of the complexity of approximate definition and calculation of functions,” in:Proceedings of the International Congress of Mathematicians, Stockholm (1963), pp. 369–376.

  2. A. N. Kolmogorov,Theory of Information and Theory of Algorithms [in Russian], Nauka, Moscow 1987.

    MATH  Google Scholar 

  3. A. Kolmogorov, “über die besste Annäherung von Funktionen either gegeben Funktionklasse,”Ann. Math.,37, 107–110 (1936).

    Article  MathSciNet  Google Scholar 

  4. A. G. Vitushkin,Estimation of the Complexity of the Problem of Tabulation [in Russian], Fizmatgiz, Moscow 1959.

    Google Scholar 

  5. Yu. Ofman, “On the algorithmic complexity of discrete functions,”Dokl. Akad Nauk SSSR,145, No. 1, 48–51 (1962).

    Google Scholar 

  6. J. F. Traub and H. Wozniakowski,A General Theory of Optimal Algorithms, Academic Press, New York 1982.

    Google Scholar 

  7. J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski,Information, Uncertainty, Complexity, Addison-Wesley, Mass. (1983).

    MATH  Google Scholar 

  8. J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski,Information-Based Complexity, Academic Pres., London (1988).

    MATH  Google Scholar 

  9. V. N. Tikhomirov,Some Problems in the Theory of Approximation [in Russian], Moscow University, Moscow 1976.

    Google Scholar 

  10. V. I. Ruban,Widths of Some Sets in Functional Spaces [in Russian], Author’s Abstract of the Candidate-Degree Thesis (Physics and Mathematics), Dnepropetrovsk (1974).

  11. N. P. Korneichuk,Exact Constants in the Theory of Approximation [in Russian], Nauka, Moscow 1987.

    Google Scholar 

  12. N. P. Korneichuk,Extremal Problems in the Theory of Approximations [in Russian], Nauka, Moscow 1976.

    Google Scholar 

  13. N. P. Korneichuk, “On the derivation of exact estimates for the derivative of spline-interpolation error,”Ukr. Mat. Zh.,43, No. 2, 206–210 (1991).

    Article  MathSciNet  Google Scholar 

  14. Yu. S. Zav’yalov, B. I. Kvasov, and V. L. Miroshnichenko,Methods of Spline Functions [in Russian], Nauka, Moscow 1980.

    MATH  Google Scholar 

  15. N. P. Korneichuk, “On optimal encoding of vector functions,”Ukr. Mat. Th.,40, No. 6, 737–743 (1988).

    MathSciNet  Google Scholar 

Download references

Authors
  1. N. P. Korneichuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Korneichuk, N.P. Complexity of approximation problems. Ukr Math J 48, 1904–1915 (1996). https://doi.org/10.1007/BF02375376

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02375376

Keywords

Search

Navigation