Computational Complexity: A Conceptual Perspective (Google eBook)

Front Cover
Cambridge University Press
1 Review
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Related books

Contents

1 Introduction and Preliminaries
1
2 P NP and NPCompleteness
44
3 Variations on P and NP
108
4 More Resources More Power?
127
5 Space Complexity
143
6 Randomness and Counting
184
7 The Bright Side of Hardness
241
8 Pseudorandom Generators
284
A Glossary of Complexity Classes
463
B On the Quest for Lower Bounds
469
C On the Foundations of Modern Cryptography
482
D Probabilistic Preliminaries and Advanced Topics in Randomization
523
E Explicit Constructions
545
F Some Omitted Proofs
566
G Some Computational Problems
583
Bibliography
589

9 Probabilistic Proof Systems
349
10 Relaxing the Requirements
416
Epilogue
461
Index
601
Copyright

Common terms and phrases

Popular passages

Page 1 - When you start on your journey to Ithaca, then pray that the road is long, full of adventure, full of knowledge.

References to this book

Bibliographic information