Information Technology Reference
In-Depth Information
This important question is related to the question whether
P
=
NP
,becauseif
NP
=
coNP
,
=
NP
because
P
is closed under complements but
NP
is not.
then
P
8.6.1 The Complement of
NP
The class
coNP
is the class of decision problems whose complements are in
NP
.Thatis,
coNP
is the language of “No” instances of problems in
NP
. The decision problem
VALIDITY
defined below is an example of a problem in
coNP
. In fact, it is log-space complete for
coNP
.
(See Problem
8.10
.)
VALIDITY
identifies SOPEs (the sum-of-products expansion, defined in
Section
2.3
) that can have value 1.
VALIDITY
Instance:
A set of literals
X
=
, and a sequence of products
P
=(
p
1
,
p
2
,
...
,
p
m
)
,whereeachproduct
p
i
is a subset of
X
.
Answer:
“Yes” if for all assignments of Boolean values to variables in
{
x
1
,
x
1
,
x
2
,
x
2
,
...
,
x
n
,
x
n
}
{
x
1
,
x
2
,
...
,
x
n
}
every
literal in at least one product has value 1.
Given a language
L
in
NP
,astringin
L
has a certificate for its membership in
L
consisting
of the set of choices that cause its recognizing Turing machine to accept it. For example, a
certificate for
SATISFIABILITY
is a set of values for its variables satisfying at least one literal
in each sum. For an instance of a problem in
coNP
,a
disqualification
is a certificate for the
complement of the instance. An instance in
co
VALIDITY
is disqualified by an assignment that
causes all products to have value 0. Thus, each “Yes” instance in
VALIDITY
is disqualified by
an assignment that prevents the expression from being valid. (See Problem
8.11
.)
As mentioned just before the start of this section, if
NP
=
coNP
,then
P
=
NP
because
P
=
coNP
,wetryto
identify a problem that is in
NP
but is not known to be in
P
. A problem that is
NP
and
coNP
simultaneously (the class
NP
is closed under complements. Because we know of no way to establish
NP
∩
coNP
) is a possible candidate for a problem that is in
NP
but
not
P
, which would show that
P
=
NP
. We show that
PRIMALITY
is in
NP
∩
coNP
.(Itis
⊆
∩
straightforward to show that
P
NP
coNP
. See Problem
8.12
.)
PRIMALITY
Instance:
An integer
n
written in binary notation.
Answer:
“Yes” if
n
is a prime.
A disqualification for
PRIMALITY
is an integer that is a factor of
n
. Thus, the complement
of
PRIMALITY
is in
NP
,so
PRIMALITY
is in
coNP
. We now show that
PRIMALITY
is also in
NP
or that it is in
NP
coNP
. To prove the desired result we need the following result from
number theory, which we do not prove (see [
235
, p. 222] for a proof ).
∩
THEOREM
8.6.3
An integer
p>
2
is prime if and only if there is an integer
1
<r<p
such that
r
p−
1
=
1
mod
p
and for all prime divisors
q
of
p
1
,
r
(
p−
1
)
/q
−
=
1
mod
p
.
As a consequence, to give evidence of primality of an integer
p>
1, we need only provide
an integer
r
,1
<r<p
, and the prime divisors
{
q
1
,
...
,
q
k
}
other than 1 of
p
−
1andthen
show that
r
p−
1
=
1
mod
p
and
r
(
p−
1
)
/q
.Bythetheorem,
such integers exist if and only if
p
is prime. In turn, we must give evidence that the integers
{
=
1
mod
p
for
q
∈{
q
1
,
...
,
q
k
}
1and
areprime.Wemustalsoshowthat
k
is small and that the recursive check of the primes does
q
1
,
...
,
q
k
}
are prime divisors of
p
−
1, which requires showing that they divide
p
−
Search WWH ::
Custom Search