Complexity and Information

Front Cover
Cambridge University Press, Dec 10, 1998 - Computers - 139 pages
0 Reviews
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.

Selected pages

Contents

Introduction
3
InformationBased Complexity
10
22 A General Formulation of IBC
14
Integration Concluded
21
Breaking the Curse of Dimensionality
24
Some Interesting Topics
41
Very HighDimensional Integration and Mathematical Finance
43
Complexity of Path Integration
53
Complexity of Linear Programming
74
Complexity of Verification
77
Complexity of Implementation Testing
83
Noisy Information
88
Value of Information in Computation
94
Assigning Values to Mathematical Hypotheses
99
Open Problems
103
A Brief History of InformationBased Complexity
105

Are IllPosed Problems Solvable?
57
Complexity of Nonlinear Problems
61
71 The Fredholm Problem of the Second Kind
62
72 Nonlinear Equations
63
What Model of Computation Should Be Used by Scientists?
65
Do Impossibility Theorems from Formal Models Limit Scientific Knowledge?
70
The Literature of IBC
109
A Guide to the Literature
111
Bibliography
112
Author index
134
Subject index
138

Other editions - View all

Common terms and phrases

Popular passages

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 [2], devoted to the representation of functions of several...
Page 116 - Mauldon, JG [1956]. General principles of antithetic variates. Proc. Cambridge Philos. Soc., 52, 476-481. Hammersley, JM & Morton, KW [1956]. A new Monte Carlo technique: Antithetic Variates. Proc. Cambridge Philos. Soc., 52, 449-475.

References to this book

All Book Search results »

Bibliographic information