Mathematics – History and Overview
Scientific paper
2009-03-11
Mathematics
History and Overview
To appear in "Essays on the Complexity of Continuous Problems: A Festschrift for Henryk Wozniakowski" by E. Novak, I. Sloan, J
Scientific paper
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.
No associations
LandOfFree
A brief history of information-based complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A brief history of information-based complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A brief history of information-based complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-124355