Abstract

Tractability of a multivariate problem with d variables means that the minimal number of functional evaluations needed to compute an approximation depends polynomially on d and ^-1. The dependence on ^-1 has been studied for years whereas the study of the dependence on d is relatively new.

We survey results on tractability of multivariate integration and approximation for weighted Sobolev and Korobov spaces. The space weights quantify the importance of successive variables in the multivariate problem. Necessary and sufficient conditions on tractability are expressed in terms of the space weights. Tractability holds iff the space weights go to zero sufficiently fast. The classical case for which the space weights are all equal leads to intractability.