Logo

Complexity Theory: A Modern Approach

Large book cover: Complexity Theory: A Modern Approach

Complexity Theory: A Modern Approach
by

Publisher: Cambridge University Press
ISBN/ASIN: 0521424267
ISBN-13: 9780521424264
Number of pages: 489

Description:
This book aims to describe such recent achievements of complexity theory in the context of the classical results. It is intended to be a text and as well as a reference for self-study. This means it must simultaneously cater to many audiences, and it is carefully designed with that goal. The book will explain the context in which a certain notion is useful, and why things are defined in a certain way. Examples and solved exercises accompany key definitions. This book assumes essentially no computational background (though a slight exposure to computing may help) and very little mathematical background apart from the ability to understand proofs and some elementary probability on finite sample spaces. A typical undergraduate course on "Discrete Math" taught in many math and CS departments should suffice (together with the Appendix).

Home page url

Download or read it online for free here:
Download link
(4.4MB, PDF)

Similar books

Book cover: P, NP, and NP-Completeness: The Basics of Complexity TheoryP, NP, and NP-Completeness: The Basics of Complexity Theory
by - 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.
(4039 views)
Book cover: Lecture Notes on Computational ComplexityLecture Notes on Computational Complexity
by
Notes from a graduate courses on Computational Complexity. The first 15 lectures cover fundamentals, the remaining is advanced material: Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, and more.
(9833 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.
(435 views)
Book cover: From Complexity to CreativityFrom Complexity to Creativity
by - Plenum Press
This text applies the concepts of complexity science to provide an explanation of all aspects of human creativity. The book describes the model that integrates ideas from computer science, mathematics, neurobiology, philosophy, and psychology.
(8986 views)