ABSTRACT
Information-based complexity (IBC) studies the complexity of infinite-dimensional continuous problems. It is a branch of computational complexity which studies the minimal computer resources needed to solve mathematically posed problems. A number of researchers have commented on the relation between science and computation. Although the following quotations are primarily about the foundations of physics, the same relation holds for other sciences. The chapter describes IBC with two other branches of computational complexity. Blum, Shub, and Smale have studied the complexity of continuous problems defined by a finite number of parameters. The chapter discusses whether noncomputability and intractability can be broken using randomization or the average-case setting and pose four open problems. It reports on the application of IBC to ill-posed problems, partial differential equations, and integral equations. The chapter shows how number theory results were used to obtain the average case complexity of multivariate integration. It explores the complexity results of Werschulz for linear elliptic differential equations.
