Information-based complexity: Difference between revisions

Revision as of 01:07, 13 April 2013

Revision as of 15:52, 11 April 2014

Line 1:

{{unreferenced|date=April 2012}}

'''Information-based complexity''' ('''IBC''') studies optimal [[algorithms]] and [[computational complexity]] for the continuous problems which arise in [[physical science]], [[economics]], [[engineering]], and [[mathematical finance]]. IBC has studied such continuous problems as [[path integration]], [[partial differential equations]], systems of [[ordinary differential equations]], nonlinear equations, [[integral equations]], [[Fixed point (mathematics)|fixed points]], and very -high-dimensional [[numerical integration|integration]]. All these problems involve functions (typically multivariate) of a real or complex variable. Since one can never obtain a closed-form solution of the problems of interest one has to settle for a numerical solution. Since a function of a real or complex variable cannot be entered into a digital computer, the solution of continuous problems involves ''partial'' information. To give a simple illustration, in the numerical approximation of an integral, only samples of the integrand at a finite number of points are available. In the numerical solution of partial differential equations the functions specifying the boundary conditions and the coefficients of the differential operator can only be sampled. Furthermore, this partial information can be expensive to obtain. Finally the information is often ''contaminated'' by noise.

The goal of information-based complexity is to create a theory of computational complexity and optimal algorithms for problems with partial, contaminated and priced information, and to apply the results to answering questions in various disciplines. Examples of such disciplines include [[physics]], economics, mathematical finance, [[computer vision]], [[control theory]], [[geophysics]], [[medical imaging]], [[weather forecasting]] and [[Numerical weather prediction|climate prediction]], and [[statistics]]. The theory is developed over abstract spaces, typically [[Hilbert space|Hilbert]] or [[Banach space|Banach]] spaces, while the applications are usually for multivariate problems.