A brief history of information-based complexity
From MaRDI portal
Publication:3656491
zbMath1186.68001arXiv0903.2037MaRDI QIDQ3656491
Publication date: 13 January 2010
Abstract: This paper was presented on the occasion of an honorary doctoral degree for Henryk Wozniakowski at Friedrich Schiller University in Jena, Germany on June 6, 2008. Information-based complexity (IBC) is the study of algorithms and computational complexity of continuous problems. Examples of such problems include partial differential equations (in particular, the Schrodinger equation) very high dimensional integration, approximation, continuous optimization, and path integration. Because the computer has only partial information about the continuous mathematical problem adversary arguments at the information level often lead to tight complexity bounds. This may be contrasted with discrete problems where only conjectures that the complexity hierarchy does not collapse are available. This paper discusses precursors to IBC. It reports on the beginning of optimal iteration theory in the early 60s which was published in Traub's 1964 monograph. In the 70s Traub and Wozniakowski began to formulate the foundations of IBC leading to their 1980 monograph. The paper continues with the development of IBC to the present.
Full work available at URL: https://arxiv.org/abs/0903.2037
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) History of computer science (68-03)
This page was built for publication: A brief history of information-based complexity
