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