Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions (Q843723)

Let \(f:[0,1]^{d}\to {\mathbb R}\) be a function which are infinitely many times differentiable with respect to all variables and have the property that the sum of all normalized derivatives is bounded in the \(L_{p}\)-norm, for some \(p\in[1,\infty)\). The authors approximate such a function with respect to the Sobolev norm \(W_{p}^{\mathbf m}([0,1]^d)\). Here \({\mathbf m}=[m,m,\dots,m]\), \(d\) times, for some non-negative integer \(m\) and the norm of the target space is defined in terms of up to \(m\) partial derivatives with respect to all \(d\) variables. The optimal order of convergence is infinite, hence excellent, but the problem is still intractable and suffers from the curse of dimensionality if \(m\geq 1\). This means that the order of convergence supplies incomplete information concerning the computational difficulty of a problem. For \(m=0\) and \(p=2\), the authors prove that the problem is not polynomially tractable, but that it is weakly tractable.