General Theory of Optimal Error Algorithms and Analytic Complexity. Part B. Iterative Information Model.

Abstract

This is the second of a series of papers in which we construct an information based general theory of optimal error algorithms and analytic computational complexity and study applications of the general theory. In our first paper we studied a general information' model; here we study an 'iterative information' model. We give a general paradigm, based on the pre-image set of an information operator, for obtaining a lower bound on the error of any algorithm using this information. We show that the order of information provides an upper bound on the order of any algorithm using this information. This upper bound order leads to a lower bound on the complexity index.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1978
Accession Number
ADA063757

Entities

People

  • H. Wozniakowski
  • Joseph F. Traub

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Analytic Functions
  • Banach Space
  • Computational Complexity
  • Computations
  • Computer Science
  • Differential Equations
  • Equations
  • Integrals
  • Iterations
  • Linear Differential Equations
  • Mathematics
  • Numbers
  • Real Numbers
  • Scalar Functions
  • Sequences
  • Stationary

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Robotics and Automation.