General Theory of Optimal Error Algorithms and Analytic Complexity. Part A. General Information Model.
Abstract
This is the first of a series of papers constructing an information based general theory of optimal errors and analytic computational complexity. Among the applications are such traditionally diverse areas as approximation, boundary-value problems, quadrature, and nonlinear equations in a finite or infinite dimensional space. Traditionally algorithms are often derived by ad hoc criteria. The information based theory rationalizes the synthesis of algorithms by showing how to construct algorithms which minimize or nearly minimize the error. For certain classes of problems it shows how to construct algorithms (linear optimal error algorithms) which enjoy essentially optimal complexity with respect to all possible algorithms. The existence of strongly non-computable problems is demonstrated. In contrast with the gap theorem of recursively computable functions it is shown that every monotonic real function is the complexity of some problem.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1977
- Accession Number
- ADA046860
Entities
People
- H. Wozniakowski
- Joseph F. Traub
Organizations
- Carnegie Mellon University