# Chapter *4*

*Structure of NP*

In order to understand the difficulty of solving the *P* versus *NP* problem, we study in this chapter the internal structure of the complexity class *NP*. We demonstrate some natural problems as candidates of incomplete problems in *NP*–*P* and study the notion of one-way functions. We also introduce the notion of relativization to help us understand the possible relations between subclasses of *NP*. One of the main proof techniques used in this study is stage-construction diagonalization, which has been used extensively in recursion theory.

## 4.1 Incomplete Problems in *NP*

We have seen many *NP*-complete problems in Chapter 2. Many natural problems in *NP* turn out to be *NP*-complete. There are, however, a few interesting problems in *NP* that are not likely to be solvable in deterministic polynomial time but also are not known to be *NP*-complete. The study of these problems is thus particularly interesting, because it not only can classify the inherent complexity of the problems themselves but can also provide a glimpse of the internal structure of the class *NP*. We start with some examples.

#### Example 4.1

Get *Theory of Computational Complexity, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.