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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
