Computational Complexity: A Conceptual Perspective
by Oded Goldreich
Publisher: Cambridge University Press 2008
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.
Download or read it online for free here:
Download link
(1.4MB, PS)
Similar books
Measure-Preserving Systemsby Karl Petersen - University of North Carolina
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(10770 views)
Complexity Theoryby Johan Håstad
This set of notes gives the broad picture of modern complexity theory, defines the basic complexity classes, gives some examples of each complexity class and proves the most standard relations. The author emphasizes the ideas involved in the proofs.
(16381 views)
P, NP, and NP-Completeness: The Basics of Complexity Theoryby Oded Goldreich - Cambridge University Press
The main focus of the current book is on the P-vs-NP Question and the theory of NP-completeness. Additional topics that are covered include the treatment of the general notion of a reduction between computational problems.
(9292 views)
Mathematics and Computationby Avi Wigderson - Princeton University Press
The book provides a broad, conceptual overview of computational complexity theory -- the mathematical study of efficient computation. It is useful for undergraduate and graduate students in mathematics, computer science, and related fields.
(3339 views)