Information-based complexity

Remarks

Example: let $F$ be the set of functions $f \colon [0,1] \to \R$ with $\abs{f(s) - f(t)} \le \abs{s - t}$, let $S(f) = \int_0^1 f(t) \, dt \in \R$, and let $\Lambda$ be the function evaluations. The midpoint rule $A(f) = \frac{1}{n} \sum_{k=1}^{n} f\big(\frac{2k-1}{2n}\big)$ has $e(A) = \frac{1}{4n}$, since on each subinterval of length $1/n$ the error is at most $\int \abs{t - c} \, dt = \frac{1}{4n^2}$, where $c$ is its midpoint. No algorithm does better, so $e(n) = \frac{1}{4n}$ and $n(\varepsilon) = \ceil{1/(4\varepsilon)}$. Non-example: the map $A(f) = \int_0^1 f$ itself has error $0$, but it uses infinitely many pieces of information. Indeed two functions in $F$ that agree at finitely many points can have different integrals. Besides the worst-case setting, there are average-case, probabilistic and randomized settings, where the supremum over $F$ is replaced by an expectation or the algorithm may use random choices. Often $\Lambda$ is the class of all continuous linear functionals on a normed space containing $F$. A problem is called polynomially tractable when $n(\varepsilon)$ for the $d$-variate version grows at most polynomially in $d$ and $1/\varepsilon$.