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: Algorithmic Randomness and ComplexityAlgorithmic Randomness and Complexity
by - Springer
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
(6728 views)
Book cover: Measure-Preserving SystemsMeasure-Preserving Systems
by - 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.
(7915 views)
Book cover: Complexity and ComputationComplexity and Computation
by - Green Tea Press
This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.
(12627 views)
Book cover: Parallel Complexity TheoryParallel Complexity Theory
by - Prentice Hall
The rapid growth of parallel complexity theory has led to a proliferation of parallel machine models. This book presents a unified theory of parallel computation based on a network model. It is the first such synthesis in book form.
(6476 views)