Information-based complexity: Difference between revisions

Revision as of 11:22, 10 April 2025

Revision as of 14:36, 10 April 2025

Line 1:

{{no footnotes|date=October 2014}}

{{merge from|Oracle complexity (optimization)|date=June 2024}}

'''Information-based complexity''' ('''IBC''') studies optimal [[algorithms]] and [[Analysis of algorithms|computational complexity]] for the continuous problems that 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 equation]]s, [[integral equations]], [[Fixed point (mathematics)|fixed points]], and very-high-dimensional [[numerical integration|integration]]. All these problems involve functions (typically multivariate) of a [[real number|real]] or [[complex number|complex]] variable. Since one can never obtain a closed-form solution to 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.