Complexity Theory - Contemporary Cryptography - page 157

In this case, the algorithm that solves D 2 serves as an oracle. 9 If D 1 ≤ P D 2 ,
then D 2 is at least as difficult as D 1 , or, equivalently, D 1 is no harder than D 2 .If
both D 1 ≤ P D 2 and D 2 ≤ P D 1 ,then D 1 and D 2 are computationally equivalent .
Polynomial-time reductions are transitive. This basically means that if D 1 ≤ P
D 2 and D 2 ≤ P D 3 ,then D 1 ≤ P D 3 .Furthermore,if D 1 ≤ P D 2 and D 2 ∈P ,then

D 1 ∈P . In either case, polynomial-time reductions are important when it comes to

prove the NP -completeness of a problem.

6.6.2.2 NP -Completeness

Loosely speaking, a decision problem D is NP -complete if it is in NP and every

decision problem in NP polytime reduces to it. This idea is captured in Definition

6.11.

} ∗ is Definition 6.11 (NP-complete problem) A decision problem D ⊆{ 0 , 1 NP -

complete if D ∈NP and D 1 ≤ P D for every decision problem D 1 ∈NP .

Note that this definition can't be used to show that a decision problem D is

NP -complete. This is because it is difficult to show the second condition for every

D 1 ∈NP . If, however, we already know that a specific decision problem D 1 is

NP -complete, then we can prove the NP -completeness of D by showing that it

is in and that it polytime reduces to D 1 . More specifically, the following three

steps can be used to prove that a decision problem D is

NP

NP -complete:

1. Prove that D ∈NP ;

2. Select a decision problem D 1 that is known to be NP -complete;

3. Prove that D 1 ≤ P D .

NP

-complete (decision) problems are “universal” in the sense
that providing a polynomial-time algorithm for solving one of them immediately
implies polynomial-time algorithms for solving all of them. More specifically, if
there exists a single

Consequently,

NP -complete decision problem that can be shown to be in

P ,then P = NP results immediately. Similarly, if there exists a single NP -

complete decision problem that can be shown in co NP

results immediately. Such a result would be extremely surprising, and a proof that a
problem is

NP ,thenco NP =

-complete generally provides strong evidence for the computational
intractability of it.
At first glance, it may be surprising that

NP

-complete problems exist. There
exist, however, many problems that are known to be

NP

NP -complete (e.g., [1]). In

9 Note that the notion of an oracle has become very important in contemporary cryptography.