Mathematics and Computation : : A Theory Revolutionizing Technology and Science / / Avi Wigderson.
An introduction to computational complexity theory, its connections and interactions with mathematics, and its central role in the natural and social sciences, technology, and philosophyMathematics and Computation provides a broad, conceptual overview of computational complexity theory-the mathemati...
Saved in:
| Superior document: | Title is part of eBook package: De Gruyter EBOOK PACKAGE COMPLETE 2019 English |
|---|---|
| VerfasserIn: | |
| Place / Publishing House: | Princeton, NJ : : Princeton University Press, , [2019] ©2019 |
| Year of Publication: | 2019 |
| Language: | English |
| Online Access: | |
| Physical Description: | 1 online resource (440 p.) :; 25 b/w illus. |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Frontmatter
- Contents
- Acknowledgments
- 1. Introduction
- 2. Prelude: Computation, undecidability, and limits to mathematical knowledge
- 3. Computational complexity 101: The basics, P, and NP
- 4. Problems and classes inside (and around) NP
- 5. Lower bounds, Boolean circuits, and attacks on P vs. NP
- 6. Proof complexity
- 7. Randomness in computation
- 8. Abstract pseudo-randomness
- 9. Weak random sources and randomness extractors
- 10. Randomness and interaction in proofs
- 11. Quantum computing
- 12. Arithmetic complexity
- 13. Interlude: Concrete interactions between math and computational complexity
- 14. Space complexity: Modeling limited memory
- 15. Communication complexity: Modeling information bottlenecks
- 16. On-line algorithms: Coping with an unknown future
- 17. Computational learning theory, AI, and beyond
- 18. Cryptography: Modeling secrets and lies, knowledge and trust
- 19. Distributed computing: Coping with asynchrony
- 20. Epilogue: A broader perspective of ToC
- References