Logo

P, NP, and NP-Completeness: The Basics of Complexity Theory

Large book cover: P, NP, and NP-Completeness: The Basics of Complexity Theory

P, NP, and NP-Completeness: The Basics of Complexity Theory
by

Publisher: Cambridge University Press
ISBN/ASIN: 0521122546
ISBN-13: 9780521122542
Number of pages: 190

Description:
The focus of this book is on the P-vs-NP Question, which is the most fundamental question of computer science, and on the theory of NP-completeness, which is its most influential theoretical discovery. The book also provides adequate preliminaries regarding computational problems and computational models.

Home page url

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

Similar books

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.
(7975 views)
Book cover: Around Kolmogorov Complexity: Basic Notions and ResultsAround Kolmogorov Complexity: Basic Notions and Results
by - arXiv.org
Algorithmic information theory studies description complexity and randomness. This text covers the basic notions of algorithmic information theory: Kolmogorov complexity, Solomonoff universal a priori probability, effective Hausdorff dimension, etc.
(4733 views)
Book cover: Complexity Theory: A Modern ApproachComplexity Theory: A Modern Approach
by - Cambridge University Press
The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.
(15812 views)
Book cover: Computability and Complexity from a Programming PerspectiveComputability and Complexity from a Programming Perspective
by - The MIT Press
The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.
(10228 views)