# P, NP, and NP-Completeness

## The Basics of Complexity Theory

### [drafts of a textbook by Oded Goldreich]

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

Below is the book's tentative preface and Organization. The following versions are available on-line.

• A preliminary draft (dated June 2008): in PostScript format.
• Revisions: May'09 and Oct'09 (also in PostScript format).

Last updated: May 2009.

#### 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.

Preface, Overview, notes "To the Teacher", a summary of "Notations and Conventions" and "Main Definitions and Results".
1.1 Representation; 1.2 Computational Tasks; 1.3 Uniform Models (Algorithms) [Turing machines, Uncomputable functions, Universal algorithms, Time and space complexity, Oracle machines, Restricted models]; 1.4 Non-uniform Models (Circuits and Advice) [Boolean Circuits, Machines that take advice, Restricted models]; 1.5 Complexity Classes
2. The P versus NP Question
2.1 Efficient Computation 2.2 The search version - finding versus checking; 2.3 The decision version - proving versus verifying; 2.4 Equivalence of the two formulations; 2.5 The traditional definition of NP; 2.6 Two technical comments regarding NP; 2.7 In support of P different from NP; 2.8 Philosophical meditations.
3. Polynomial-time Reductions
3.1 The general notion of a reduction; 3.2 Reducing optimization problems to search problems; 3.3 Self-reducibility of search problems; 3.4 Digest and general perspective.
4. NP-Completeness
4.1 Definitions; 4.2 The existence of NP-complete problems; 4.3 Some natural NP-complete problems [Circuit and formula satisfiability - CSAT and SAT, Combinatorics and graph theory, additional properties of standard reductions, on the negative application of NP-completeness, positive applications of NP-completeness]; 4.4 NP sets that are neither in P nor NP-complete; 4.5 Reflections on complete problems.
5.1 Promise Problems; 5.2 Optimal search algorithms for NP; 5.3 The class coNP and its intersection with NP.
Notes
Epilogue: A brief overview of Complexity Theory
Appendix - Some Computational Problems [A.1 Graphs; A.2 Formulae]
Bibliography