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

Oded Goldreich

cover

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.
The P-vs-NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. Whilst the P-vs-NP Question remains unresolved, the theory of NP-completeness offers evidence to the intractability of specific problems in NP by showing that they are universal for the entire class.

ISBN 978-0-521-12254-2
Published in US in 2010.
Publisher: Cambridge University Press
(see the publisher's page for this volume).

The current textbook is a significant revision of Chapter 2 and Section 1.2 of the author's book Computational Complexity: A Conceptual Perspective.

Below is the book's tentative preface and Organization. Drafts (and additional related texts) are available from HERE. See also list of corrections and additions (to the print version).

Last updated: August 2010.


Preface (tentative, June 2008)

The strive for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience.

A key step towards the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by computability theory, which emerged in the 1930's. This theory focuses on computational tasks, and considers automated procedures (i.e., computing devices and algorithms) that may solve such tasks.

In focusing attention on computational tasks and algorithms, computability theory has set the stage for the study of the computational resources (like time) that are required by such algorithms. When this study focuses on the resources that are necessary for any algorithm that solves a particular task (or a task of a particular type), the study becomes part of the theory of Computational Complexity (also known as Complexity Theory).

Complexity Theory is a central field of the theoretical foundations of Computer Science. It is concerned with the study of the intrinsic complexity of computational tasks. That is, a typical Complexity theoretic study refers to the computational resources required to solve a computational task (or a class of such tasks), rather than referring to a specific algorithm or an algorithmic schema. Actually, research in Complexity Theory tends to start with and focus on the computational resources themselves, and addresses the effect of limiting these resources on the class of tasks that can be solved. Thus, Computational Complexity is the general study of the what can be achieved within limited time (and/or other limited natural computational resources).

The most famous question of complexity theory is the P-vs-NP Question, and the current book is focused on it. The P-vs-NP Question can be phrased as asking whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness; that is, is proving harder than verifying. The fundamental nature of this question is evident in each of these formulations, which are in fact equivalent. It is widely believed that the answer to these equivalent formulations is that finding (resp., proving) is harder than checking (resp., verifying); that is, it is believed that P is different from NP.

At present, when faced with a hard problem in NP, we can only hope to prove that it is not in P assuming that NP is different from P. This is where the theory of NP-completeness, which is based on the notion of a reduction, comes into the picture. In general, one computational problem is reducible to another problem if it is possible to efficiently solve the former when provided with an (efficient) algorithm for solving the latter. A problem (in NP) is NP-complete if any problem in NP is reducible to it. Amazingly enough, NP-complete problems exist, and furthermore hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete.

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, which provides a tighter relation between the aforementioned search and decision problems. The book also provides adequate preliminaries regarding computational problems and computational models.

The current book is a significant revision of Chapter 2 and Section 1.2 of the author's book Computational Complexity: A Conceptual Perspective The revision was aimed at making the book more friendly to the novice. In particular, numerous technical expositions were further detailed and many exercises were added.

Table of contents (revised Oct'09)


List of Corrections and Additions


©Copyright 2008 by Oded Goldreich.
Permission to make copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.


Back to Oded Goldreich's homepage.