Logo

Computational Complexity: A Conceptual Perspective

Large book cover: Computational Complexity: A Conceptual Perspective

Computational Complexity: A Conceptual Perspective
by

Publisher: Cambridge University Press
ISBN/ASIN: 052188473X
ISBN-13: 9780521884730
Number of pages: 632

Description:
This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. The book can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.

Home page url

Download or read it online for free here:
Download link
(1.4MB, PS)

Similar books

Book cover: Algorithms and ComplexityAlgorithms and Complexity
by - AK Peters, Ltd.
An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.
(12881 views)
Book cover: Communication Complexity (for Algorithm Designers)Communication Complexity (for Algorithm Designers)
by - Stanford University
The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
(1262 views)
Book cover: Think Complexity: Complexity Science and Computational ModelingThink Complexity: Complexity Science and Computational Modeling
by - Green Tea Press
This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.
(4898 views)
Book cover: Computability and ComplexityComputability and Complexity
- Wikibooks
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is CS and Math students with some background in programming and data structures.
(4427 views)