Information Technology Reference
In-Depth Information
O
(
n
5
)
RAM steps suffice to verify
p
. Since a polynomial number of RAM steps can be
executed in a polynomial number of Turing machine steps,
PRIMALITY
is in
NP
.
∩
⊆
∩
⊆
⊆
∪
Since
NP
coNP
NP
and
NP
coNP
coNP
as well as
NP
NP
coNP
and
⊆
∪
coNP
NP
coNP
, we begin to have the makings of a hierarchy. If we add that
coNP
⊆
PSPACE
(see Problem
8.13
), we have the relationships between complexity classes shown
schematically in Fig.
8.7
.
8.7 Reductions
In this section we specialize the reductions introduced in Section
2.4
and use them to classify
problems into categories. We show that if problem
A
is reduced to problem
B
by a function
in the set
R
and
A
is hard relative to
R
,then
B
cannot be easy relative to
R
because
A
can
be solved easily by reducing it to
B
and solving
B
with an easy algorithm, contradicting the
fact that
A
is hard. On the other hand, if
B
is easy to solve relative to
R
,then
A
must be
easy to solve. Thus, reductions can be used to show that some problems are hard or easy. Also,
if
A
can be reduced to
B
by a function in
R
and vice versa, then
A
and
B
have the same
complexity relative to
R
.
Reductions are widely used in computer science; we use them whenever we specialize one
procedure to realize another. Thus, reductions in the form of simulations are used throughout
Chapter
3
to exhibit circuits that compute the same functions that are computed by finite-
state, random-access, and Turing machines, with and without nondeterminism. Simulations
prove to be an important type of reduction. Similarly, in Chapter
10
we use simulation to show
that any computation done in the pebble game can be simulated by a branching program.
Not only did we simulate machines with memory by circuits in Chapter
3
, but we demon-
strated in Sections
3.9.5
and
3.9.6
that the languages
CIRCUIT VALUE
and
CIRCUIT SAT
describing circuits are
P
-complete and
NP
-complete, respectively. We demonstrated that each
string
x
in an arbitrary language in
P
(
NP
) could be translated into a string in
CIRCUIT VALUE
(respectively,
CIRCUIT SAT
) by a program whose running time is polynomial in the length of
x
and whose space is logarithmic in its length.
In this chapter we extend these results. We consider primarily transformations (also called
many-one reductions
and just
reductions
in Section
5.8.1
), a type of reduction in which an
instance of one decision problem is translated to an instance of a second problem such that the
former is a “yes” instance if and only if the latter is a “yes” instance. A
Tu r i n g r e d u c t i o n
is a
second type of reduction that is defined by an oracle Turing machine. (See Section
8.4.2
and
Problem
8.15
.) In this case the Turing machine may make more than one call to the second
problem (the oracle). A transformation is equivalent to an oracle Turing reduction that makes
one call to the oracle. Turing reductions subsume all previous reductions used elsewhere in this
topic. (See Problems
8.15
and
8.16
.) However, since the results of this section can be derived
with the weaker transformations, we limit our attention to them.
DEFINITION
8.7.1
If
L
1
and
L
2
are languages, a
transformation
h
from
L
1
to
L
2
is a DTM-
computable function
h
:
B
∗
→B
∗
such that
x
L
2
.A
resource-
bounded transformation
is a transformation that is computed under a resource bound such as
deterministic logarithmic space or polynomial time.
∈
L
1
if and only if
h
(
x
)
∈
Search WWH ::
Custom Search