Randomization for continuous problems (Q1122297)

The author deals with the computational complexity compran(\(\epsilon)\) for continuous problems with random methods, allowing the functional evaluations and the number of such evaluations to be chosen randomly with any arbitrary distribution. Integration problems are studied for which a sharp complexity lower bound is unknown. An approximation (with an error not exceeding \(\epsilon)\) is sought to \(S(f)=\int_{[0,1]^ d}f(x)dx\) for any function f: [0,1]\({}^ d\to {\mathbb{R}}\), whose derivatives up to order r are uniformly bounded in sup-norm (r\(\geq 0\) denotes regularity of f, \(d\geq 1\) is the number of variables in f). Then maximum, i.e. \(S(f)=\max_ xf(x),\) extremal point \(S(f)\in \arg \max_ xf(x),\) function inverse \(S(f)=f^{-1},\) topological degree \(S(f)=\deg (f),\) and linear problems on Hilbert spaces with unrestricted linear information are discussed.