Complexity and Information
The twin themes of computational complexity and information pervade this book. It starts with an introduction to information-based complexity, that is, the computational complexity of continuous mathematical models. It then moves to a variety of topics, including breaking the curse of dimensionality, complexity of path integration, solvability of ill-posed problems, value of information in computation, assigning values to mathematical hypotheses, and mathematical finance. The style is informal, and the goal is motivation and insight. Precise statements and proofs can be found in the monographs and papers included in the comprehensive bibliography. The book will be essential reading for researchers in the many disciplines influenced by the computational complexity of continuous problems.
What people are saying - Write a review
We haven't found any reviews in the usual places.
22 A General Formulation of IBC
Breaking the Curse of Dimensionality
Some Interesting Topics
Very HighDimensional Integration and Mathematical Finance
Complexity of Path Integration
Complexity of Linear Programming
Complexity of Verification
Complexity of Implementation Testing
Value of Information in Computation
Assigning Values to Mathematical Hypotheses
A Brief History of InformationBased Complexity
Are IllPosed Problems Solvable?
Complexity of Nonlinear Problems
71 The Fredholm Problem of the Second Kind
72 Nonlinear Equations
What Model of Computation Should Be Used by Scientists?
Do Impossibility Theorems from Formal Models Limit Scientific Knowledge?
Other editions - View all
approximation assume average case setting bound break intractability Chapter class F class of integrands combinatory comp(e computational complexity compute an e-approximation compwor(e continuous functions cost curse of dimensionality defined depends deterministic dimension e-complexity equations example finite number finite state machine function evaluations Gaussian measure Hence ill-posed problems information complexity information operations information-based complexity input integration problem linear functional Lipschitz Math mathematical finance mathematical model MC algorithm model of computation monograph Monte Carlo algorithm mutual information noisy information non-computable nonadaptive Novak number of tests Open Problem optimal algorithm Packel partial information path integration Plaskota polynomial prob problem elements problem is tractable pseudorandom QMC algorithms radius of information randomized setting real numbers real-number model sample points smoothness solution operator solvable solve space stochastic strongly tractable Suppose theorem theory tion trapezoidal rule Traub & Wozniakowski Turing machine Turing machine model unsolvable value of information verification Wasilkowski Wiener measure worst case setting
Page 115 - Berger, JO (eds), Statistical Decision Theory and Related Topics IV, vol. 1. New York: Springer- Verlag.
Page 119 - From (242) it follows in particular that logff.(3>fi(C))~l. (243) (243) is a sharpened form of formula (237) for the space under consideration. APPENDIX I THE THEOREM OF AG VITUSKIN ON THE IMPOSSIBILITY OF REPRESENTING FUNCTIONS OF SEVERAL VARIABLES BY SUPERPOSITION OF FUNCTIONS OF A SMALLER NUMBER OF VARIABLES The first sketch of the theory outlined in this article was given by one of the authors as a commentary to the work of AG Vituskin , devoted to the representation of functions of several...