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.

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.

Start Free Trial

No credit card required