Recent results and open problems in analytic computational complexity
Information and Computation
The paper is an exposition of the information-centered approach to problems that are solved with uncertainty. The theory and application of the information-centered is called -complexity. The authors have introduced the basic quanities and fundamental invariant which they call the radius of information and which tells how well a problem can be solved. They present this quantities and contrast the informationcentered approach with the algorithm-centered approach.
Page 1