O'Reilly logo

Theory of Computational Complexity, 2nd Edition by Ker-I Ko, Ding-Zhu Du

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 NPP 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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required