Complexity in Computer Science

Inbunden, Engelska, 2026

963 kr

Kommande

Beskrivning

Computational complexity theory is about the fundamental capabilities and limitations of efficient computation. Framing the subject in the broader context of computer science, this guidebook is both a self-contained tutorial for beginning graduate students in all areas of computer science and a thorough reference for specialists. Using only elementary discrete math, the book rigorously covers the central concepts of time, space, and randomness in computing, as well as connections to other areas of computer science such as cryptography and machine learning. Intuitions and general techniques are emphasized. The book features full proofs, numerous concrete examples and illustrations, and hundreds of exercises.

Produktinformation

Utgivningsdatum:2026-11-30
Vikt:500 g
Format:Inbunden
Språk:Engelska
Antal sidor:765
Förlag:Cambridge University Press
ISBN:9781009752336

Utforska kategorier

Mer om författaren

Thomas Watson is Associate Professor of Computer Science at the University of Memphis. He received his Ph.D. from the University of California, Berkeley. His research spans many areas of computational complexity and has been supported by an NSF CAREER award.

Recensioner i media

'Watson's Complexity in Computer Science is a comprehensive introduction to computational complexity. It is especially well suited for students new to the area who want to learn both the foundations of the field and its connections to other areas of computer science, such as cryptography and learning theory. Its breadth and level of detail make it an invaluable resource for students.' Shachar Lovett, University of California, San Diego

Innehållsförteckning

Prologue; Part I. Time and Space: 1. Efficient computation; 2. Time complexity; 3. Space complexity; 4. A time-space lower bound; 5. Nonuniformity; 6. Parallelism; Part II. Randomness: 7. Randomized computation; 8. Hashing; 9. Error correcting codes; 10. Heuristics; 11. Pseudorandomness; Part III. Scope of Complexity: 12. Cryptography; 13. Learning; 14. Optimization; 15. Verification; Part IV. Concrete Models: 16. Decision trees and branching programs; 17. Communication protocols; 18. Circuits and formulas; Epilogue; Appendix. Discrete math background; References; Index.