Information-based complexity

Information-based complexity (IBC) studies optimal algorithms and 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 equations, integral equations, fixed points, and very-high-dimensional integration. All these problems involve functions (typically multivariate) of a real or 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 informati

Comment
enInformation-based complexity (IBC) studies optimal algorithms and 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 equations, integral equations, fixed points, and very-high-dimensional integration. All these problems involve functions (typically multivariate) of a real or 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 informati
Has abstract
enInformation-based complexity (IBC) studies optimal algorithms and 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 equations, integral equations, fixed points, and very-high-dimensional integration. All these problems involve functions (typically multivariate) of a real or 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. 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 climate prediction, and statistics. The theory is developed over abstract spaces, typically Hilbert or Banach spaces, while the applications are usually for multivariate problems. Since the information is partial and contaminated, only approximate solutions can be obtained. IBC studies computational complexity and optimal algorithms for approximate solutions in various settings. Since the worst case setting often leads to negative results such as unsolvability and intractability, settings with weaker assurances such as average, probabilistic and randomized are also studied. A fairly new area of IBC research is continuous quantum computing.
Is primary topic of
Information-based complexity
Label
enInformation-based complexity
Link from a Wikipage to an external page
www.cs.columbia.edu/~ap
www.cs.columbia.edu/~traub
www.elsevier.com/wps/find/journaldescription.cws_home/622865/description%23description
octopus.library.cmu.edu/Collections/traub62/box00021/fld00024/bdl0002/doc0001/doc_21b24f2b1.pdf
www.cs.columbia.edu/~traub/
www.amazon.com/dp/0521485061/
www.ibc-research.org
Link from a Wikipage to another Wikipage
Algorithms
Analysis of algorithms
Banach space
Category:Computational complexity theory
Collateralized mortgage obligation
Columbia University
Complex number
Computer vision
Continuous-variable quantum information
Control theory
Curse of dimensionality
Domain knowledge
Economics
Engineering
Fixed point (mathematics)
Fundamental theorem of calculus
Geophysics
Hilbert space
Integer factorization
Integral equations
Joseph F Traub
Low-discrepancy sequence
Mathematical finance
Medical imaging
Monte Carlo method
Nonlinear equation
Nonlinearity
Numerical integration
Numerical weather prediction
Ordinary differential equations
Partial differential equations
Path integration
Physical science
Physics
Quasi-Monte Carlo method
Real number
Statistics
Travelling salesman problem
Weather forecasting
SameAs
4mxHF
m.026wpgc
Q6030626
তথ্য-ভিত্তিক জটিলতা
Subject
Category:Computational complexity theory
WasDerivedFrom
Information-based complexity?oldid=1116392336&ns=0
WikiPageLength
17094
Wikipage page ID
8221717
Wikipage revision ID
1116392336
WikiPageUsesTemplate
Template:Cite book
Template:Interlanguage link
Template:No footnotes