Cryptography Reference
In-Depth Information
fact, there are thousands of
-complete problems, coming from a wide range of
mathematical and scientific disciplines and fields of study. For example, deciding
whether a Boolean formula is satisfiable and deciding whether a directed graph
has a Hamiltonian cycle are both NP-complete decision problems. Furthermore, the
subset sum problem is NP-complete and has been used as a basis for many public
key cryptosystems in the past (i.e., knapsack-based cryptosystems). The subset sum
problem is that given a set of positive integers
NP
and a positive integer
s
, determine whether or not there is a subset of the
a
i
that sum to
s
.
{
a
1
,a
2
,...,a
n
}
Figure 6.2
The conjectured relationship between
P
,
NP
,co
NP
,and
NPC
.
NP
The class of all
-complete (decision) problems is sometimes also denoted
by
NPC
. Figure 6.2 illustrates the conjectured relationship between the complexity
classes
P
,
NP
,co
NP
,and
NPC
. Again, we know that
P⊆NP
and
P⊆
co
NP
,
as well as
NPC⊆NP
. We do not know, however, whether
P
=
NP
,
P
=co
NP
,
or
. Most experts believe that the answers to the last three
questions is no (but nothing along these lines has been proven).
Last but not least, one sometimes attributes the term
P
=
NP ∩
co
NP
-hard to a problem
(not necessarily a decision problem). Referring to Definition 6.11, a problem is
called
NP
-hard if the second but not necessarily the first condition is satisfied,
meaning that any decision problem in
NP
NP
polytime reduces to it (or there is at least
one
-complete problem that polytime reduces to it, respectively). For example,
finding a satisfying assignment for a Boolean formula or finding a Hamiltonian
cycle in a directed graph are NP-hard problems. We can also revisit the subset sum
problem mentioned earlier. Given positive integers
NP
and a positive
integer
s
, a computational version of the subset sum problem would ask for a subset
of the
a
i
that sum up to
s
, provided that such a subset exists. This problem can also
be shown to be
{
a
1
,a
2
,...,a
n
}
NP
-hard.
