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: Introduction to Complexity TheoryIntroduction to Complexity Theory
by
Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.
(5736 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.
(967 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.
(4621 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.
(1090 views)