Abstract:

The order of computational complexity of all bounded linear functional approximation
problem is determined for the generalized Sobolev class W
p (Id), Nikolskii
class Hk
1(Id) in the worst (deterministic), stochastic and average case setting, from which
it is concluded that the bounded linear functional approximation problem for the classes
W
p (Id) and Hk
1(Id) is intractable in worst case setting, but is tractable with respect to
stochastic and average case setting.

Key words: Worst (deterministic) case, stochastic case, average case setting, bounded
linear functional, error estimate