## Complexity and InformationThe 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.

### 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 |

134 | |

138 | |

### Other editions - View all

### Common terms and phrases

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

### 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.