Some Basic Information on Information-Based Complexity Theory
Abstract
A branch of Complexity Theory called Information-Based Complexity Theory (IBCT), produces an abundance of impressive results about the quest for approximate solutions to mathematical problems. Why then do most numerical analysts turn a cold shoulder to IBCT? Close analysis of two papers representative of IBCT's best efforts reveals a mixture of nice new observations, misdirected examples and misleading theorems. Some elements in the framework of IBCT, erected to support a rigorous yet flexible theory, make it difficult to judge whether a model is off-target or reasonably realistic. For instance, a sharp distinction is made between information and algorithms restricted to this information. Yet the information itself usually comes from an algorithm and so the distinction clouds the issues and can lead to true but misleading inferences. Another troublesome aspect of IBCT is a free parameter F, the class of admissible problem instances, whose membership fee is completely ignored in ascertaining the cost of solving the worst case in F. Sometimes this leads to unrealistic models. We conclude that one's satisfaction with each result of IBCT must be inversely proportional to what one knows about the problem. The surprising results known to us pertain only to unnatural situations and IBCT's genuinely new insights might serve us better if expressed in the conventional mode of error bounds and approximation theory.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1989
- Accession Number
- ADA256585
Entities
People
- Beresford Parlett
Organizations
- University of California, Berkeley