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

摘要

This is the second of a series of papers in which the authors 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 the authors studied a general information' model; here the authors study an 'iterative information' model. The authors 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. The authors 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.