Skip to Main Content
Theory of Computational Complexity, 2nd Edition
book

Theory of Computational Complexity, 2nd Edition

by Ding-Zhu Du, Ker-I Ko
June 2014
Intermediate to advanced content levelIntermediate to advanced
512 pages
17h 55m
English
Wiley
Content preview from Theory of Computational Complexity, 2nd Edition

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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Theory of Computation

Theory of Computation

George Tourlakis

Publisher Resources

ISBN: 9781118594971Purchase book