ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 41, 65, 68 Korneichuk, Nikolaj P., Institute of Mathematics, Kiev, Ukraine Informative aspects in Approximation Theory and Complexity of recovery Problems Let X = (X, ρ) be a metric space, X′ is the set of defined on X continuous functionals, M_{N} = {μ_{1}, μ_{2}, …, μ_{N}} ⊂ X′ and for x ∈ X M_{N}(x) = {μ_{1}(x), μ_{2}(x), …, μ_{N}(x)}. Minimal error of recovery for x ∈ 𝔐 ⊂ X is

γ^{N}(𝔐, X) = inf_{M_{N} ⊂X′} sup{ρ(x, y) : x, y ∈ 𝔐, M_{N}(x) = M_{N}(y)}.

We consider the following problems.

a) Informativeness of set M_{N} ⊂ X′ as a measure of decrease of the uncertainty domain for x ∈ 𝔐 at the expense for M_{N}(x).

b) Adaptive method of successive choice of functionals when by the select functional μ_{K} we take into account μ_{1}(x) … μ_{K−1}(x).

c) Complexity of the approximation problem as minimal quantity of ressources which is necessary for recovery element x with defined exactness. Concerning of form of the information we take following two postulates: value informative operator is number vector {c_{1}, c_{2}, …, c_{N}} ⊂ R^{N} and informative operator is continuous. Let X, Y are metric space, A is set of continuous operators from X to Y. If elements x ∈ X, y ∈ Y, A ∈ A put in touch with equality Ax = y then information about two from they determine the uncertainty domain for third. We consider three problems of the recovery in the general case and in the case when Ax = ∫_{0}^{1} K(t, u) x(t) dt.