Approximation of infinitely differentiable multivariate functions is intractable (Q2272156): Difference between revisions

Let \(F_d\) be a normed linear space of functions \(f:[0,1]^d\to\mathbb R\) that are infinitely differentiable endowed with the norm \(\|f\|_{F_d}=\sup_\alpha \|D^\alpha f\|_\infty<\infty\). Let \(A_{n,d}(f)=\varphi_n(L_1(f),\dots,L_n(f))\), where \(\varphi_n:\mathbb R^n\to L_\infty ([0,1]^d)\) is a linear or non-linear mapping, and \(L_j\) is an arbitrary continuous functional whose choice may depend on the previous values \(L_1(f),\dots,L_{j-1}(f)\). The worst case error of \(A_{n,d}\) is \(e^{\text{wor}}(A_{n,d})=\sup_{\|f\|_{F_d}\leq 1}\|f-A_{n,d}(f)\|_\infty\), and the \(n\)th minimal error is \(e(n,d)=\inf_{A_{n,d}}e^{\text{wor}}(A_{n,d})\). The minimal number of information operations needed to solve the problem to within \(\varepsilon\) is \(n(\varepsilon,d)=\min\{n:e(n,d)\leq \varepsilon\}\). A problem is weakly tractable if \(\lim_{\varepsilon^{-1}+d\to \infty}\ln\,n(\varepsilon,d)/(\varepsilon^{-1}+d)=0\), and intractable when the above relation does not hold. If \(n(\varepsilon,d)\) depends exponentially on \(d\), then it is said that the problem suffers from the curse of dimensionality. Moreover, a problem is polynomially tractable if there exist \(C,p,q>0\) such that \(n(\varepsilon,d) \leq C\varepsilon ^{-p}d^q\), for all \(\varepsilon \in (0,1)\), and \(d\in\mathbb N\). \textit{F. L. Huang} and \textit{S. Zhang} [J. Complexity 23, No.~1, 73--81 (2007; Zbl 1108.41024)] conjectured that this \(L_\infty\)-approximation problem is not polynomially tractable, and this paper is devoted to prove this conjecture and somewhat even stronger: the problem is not weakly tractable. The result is the following: For this problem \(e(n,d)=1\) for all \(n=0,1,\dots,2^{[d/2]}-1\). Therefore \(n(\varepsilon,d)\geq 2^{[d/2]}\) for all \(\varepsilon \in (0,1)\) and \(d\in\mathbb N\), and \(L_\infty\)-approximation is intractable and suffers from the curse of dimensionality.