Cryptography Reference
In-Depth Information
another possibility to define the complexity class
NP
is captured in Definition 6.8.
It basically says that a decision problem is in
NP
if a yes answer can at least be
verified efficiently.
Definition 6.8 (Complexity class
NP
)
The complexity class
NP
refers to the
}
∗
for which a yes answer can be verified
in polynomial time given some extra information, called a
certificate
or
witness
.
class of decision problems
D
⊆{
0
,
1
, then it may not be
the case that a certificate for a yes answer can be obtained easily. What is asserted
is only that such a certificate exists, and, if known, can be used to efficiently verify
the yes answer. For example, the problem of deciding whether a positive integer
n
is composite (i.e., whether there exist integers 1
<p
1
,p
2
,...,p
k
∈
N
It must be emphasized that if a decision problem is in
NP
such that
n
=
p
1
p
2
...p
k
) belongs to
. This is because if
n
is composite, then this fact
can be verified in polynomial time if one is given a divisor
a
of
n
(in this case, the
certificate is a divisor
p
i
for 1
NP
k
).
It is not clear whether the existence of an efficient verification algorithm for
yes answers also implies the existence of an efficient verification algorithm for no
answers. Consequently, there is room for a complementary complexity class co
≤
i
≤
NP
as suggested in Definition 6.9.
Definition 6.9 (Complexity class co
NP
)
The complexity class co
NP
refers to the
}
∗
for which a no answer can be verified in
polynomial time given some extra information, called a
certificate
or
witness
.
class of decision problems
D
⊆{
0
,
1
NP
NP
. Note, however, that this is only a
conjecture, and that nobody has been able to prove it (or the converse) so far.
NP
It is conjectured that co
=
NP
) refers to the class of decision problems for which a yes (no)
answer can be verified in polynomial time given an appropriate certificate. Contrary
to that,
(co
consists of the class of decision problems for which an answer can be
found in polynomial time. Consequently, we know that
P
P⊆NP
and
P⊆
co
NP
.
We do not know, however, whether the existence of an efficient verification
algorithm for decision problems (be it for yes or no answers) also implies the ability
