From the introduction:
There has been an increasing interest in studying
computational aspects of high dimensional problems.
Such problems are defined on spaces of functions of $d$ variables
and occur in many applications, with $d$ that can be hundreds or
even thousands.
The solutions of many high dimensional problems are difficult
to obtain or even to approximate.
Typically, the cost of solving these problems increases exponentially
with the dimension $d$.
This is true for numerical integration, optimal recovery, global optimization,
and for differential and integral equations over most classical
function spaces. However, this is {\it not} true for systems of
ordinary differential equations and for convex optimization,
see \cite{TW98} for a survey.
For example, the minimal error for integration of $C^r$-functions
in one variable is of order $n^{-r}$, where $n$ is the number of function
samples used by the algorithm.
Using product rules, it is easy to obtain an error of order
$n^{-r/d}$ in dimension $d>1$. It is known that the exponent
$r/d$ is best possible. Hence, if we want to guarantee an error $\e$
we must take $n$ of order $\e^{-d/r}$. For fixed regularity $r$,
this is an exponential function of $d$. For large $d$, we cannot
afford to sample the function so many times. This exponential dependence
is called {\it intractability} or the {\it curse of dimensionality};
the latter notion goes back to Bellman, see \cite{Be57}.
It is natural to ask which high dimensional problems are {\it tractable}
and which are {\it intractable}. Tractability means that
there is an algorithm that approximates
the solution with error $\e$ using $n=n(\e,d)$ samples
of the function, where $n(\e,d)$ is
polynomially bounded in $\e^{-1}$ and $d$.
If $n(\e,d)$ has a bound independent of $d$ and polynomially dependent on
$\e^{-1}$ then we have {\it strong tractability}. The number $n(\e,d)$ of
samples is usually directly related to the cost of an algorithm, and
therefore tractability means that we can solve the problem to within $\e$
in cost polynomially dependent on $\e^{-1}$ and $d$. The error $\e$
of an algorithm can be defined in various settings including the worst case,
average case, randomised or probabilistic settings.
This definition is similar
to the notion of tractability for discrete
problems using the Turing machine as a model of computation.
To prove the lack of the existence of polynomial-time algorithms for a number
of discrete problems is at the core of theoretical computer science.
This is the essence of the famous conjecture P$\not=$NP.
According to Steve Smale,
see \cite{Sm98}, the question of whether P$\not=$NP holds
is one of the three most important problems in
mathematics.
However, we use the real number model with oracles
in our study, see \cite{BSS89, BCSS98, MM97, No95,TWW88,TW80}.
In this model we assume that we can exactly compute
arithmetic operations over reals, comparisons of real numbers
and function values as oracles. This model is typically used
for numerical and scientific computations since it is an abstraction
of floating point arithmetic in fixed precision. More about
this model of computation can be found in
\cite{NW96, NW99a,NW00, We98,Wo98}.
The subject of tractability and strong tractability
for high dimensional problems over the real
number model with oracles was introduced in \cite{Wo94a} and \cite{Wo94b}.
Today this topic is being thoroughly studied in information-based
complexity and a number of characterisation results have been recently
obtained, see \cite{BG99, HNWW99, HW99, No99a, No99b, NSW97,
NW99b, SW97, SW98, WW95, WW96, WW99, Wo94a, Wo94b, Wo99}.
The notion of strong tractability seems
very demanding and one may suspect that only trivial problems are
strongly tractable. Indeed, many problems defined over classical
function spaces are not strongly tractable or even not tractable.
Sometimes, the same
problems become strongly tractable over function spaces
with suitable weights that moderate the behaviour with respect to
successive components. This subject will be explained in detail later.
To simplify the exposition we restrict ourselves primarily only
to the very important problem of
high dimensional integration in the worst case setting.
For some classes of functions
integration is related to various notions of {\it discrepancy},
which is widely used and studied in many areas such as number theory,
approximation, stochastic analysis, combinatorics,
ergodic theory and numerical analysis.
The notion of discrepancy is related
to Sobolev spaces, Wiener measure, VC dimension and Ramsey theory, see
\cite{BC87, BS95, DT97, FH96, La98a, Ma99, Ni92, NX98, Th99, Wo91}.
This paper is a survey and proofs are only sketched or completely skipped.
We will present a few classical results from the theory of numerical
quadrature. Most results, however, are quite recent since most
classical error estimates do not address the
dependence on $d$. They contain unknown factors that depend on
dimension and often increase exponentially with $d$.
If we want to establish tractability, we must know how the error
depends on $d$. Therefore we need to revisit all the classical problems and
seek sharp estimates also in terms of $d$.
Tractability of multivariate integration obviously depends on the
class of functions. We will consider a number of classes
and present three types of results:
Classes of functions for which multivariate integration
is intractable and suffers the curse of dimensionality.
This will be done by establishing exponential lower bounds in
$d$ on the number of function samples.
Classes of functions for which multivariate integration
is tractable or strongly tractable.
This will be done by proving the {\it existence}
of polynomial-time algorithms by non-constructive arguments.
Classes of functions for which multivariate integration
is tractable or strongly tractable.
This will be done by {\it constructing}
polynomial-time algorithms.
For problems belonging to the first case we {\it prove}
intractability. This is in contrast to discrete complexity theory,
where it is only {\it believed}, not proved,
that certain problems are difficult
(in the sense of exponential lower bounds).
An important area for future research is to move problems from
the second to the third case. That is, to provide {\it constructive}
algorithms for problems where we currently have only existence.
Obviously, we are especially interested in the case when the
construction is simple and does not involve extensive precomputations.
Classical algorithms are often based on grids, and the computing
time is exponential in the dimension for such algorithms. Only
algorithms based on non-grids may have the computing time bounded
by a polynomial in the dimension.
FoCM Proceedings, Oxford, July 1999.