Information Technology Reference
In-Depth Information
The classification of problems is simplified by considering classes of transformations. These
classes will be determined by bounds on resources such as space and time on a Turing machine
or circuit size and depth.
DEFINITION
8.7.2
For decision problems
P
1
and
P
2
, the notation
P
1
≤
R
P
2
means that
P
1
can
be transformed to
P
2
byatransformationintheclass
R
.
Compatibility among transformation classes and complexity classes helps determine con-
ditions under which problems are hard.
DEFINITION
8.7.3
Let
C
be a complexity class,
R
a class of resource-bounded transformations, and
P
1
and
P
2
decision problems. A set of transformations
R
is
compatible
with
C
if
P
≤
R
P
1
2
and
P
∈
C
,then
P
∈
C
.
2
1
≤
p
) are compatible
with
P
. (See Problem
8.17
.) Also compatible with
P
are the
log-space transformations
(de-
noted
It is easy to see that the
polynomial-time transformations
(denoted
≤
log
-
space
) associated with transformations that can be computed in logarithmic space.
Log-space transformations are also polynomial transformations, as shown in Theorem
8.5.8
.
8.8 Hard and Complete Problems
Classes of problems are defined above by their use of space and time. We now set the stage for
the identification of problems that are hard relative to members of these classes. A few more
definitions are needed before we begin this task.
DEFINITION
8.8.1
Aclass
R
of transformations is
transitive
if the composition of any two trans-
formations in
R
is also in
R
and for all problems
P
P
P
P
≤
R
P
P
≤
R
P
1
,
2
,and
3
,
2
and
1
2
3
P
≤
R
P
implies that
3
.
1
If a class
R
of transformations is transitive, then we can compose any two transformations
in the class and obtain another transformation in the class. Transitivity is used to define hard
and complete problems.
The transformations
≤
p
and
≤
log
-
space
described above are transitive. Below we show
≤
log
-
space
is transitive and leave to the reader the proof of transitivity of
≤
p
and the
that
polynomial-time Turing reductions. (See Problem
8.19
.)
THEOREM
8.8.1
Log-space transformations are transitive.
Proof
A log-space transformation is a DTM that has a read-only input tape, a write-only
output tape, and a work tape or tapes on which it uses
O
(log
n
)
cells to process an input
string
w
of length
n
. As shown in Theorem
8.5.8
, such DTMs halt within polynomial time.
We now design a machine
T
that composes two log-space transformations in logarithmic
space. (See Fig.
8.10
.)
Let
M
1
and
M
2
denote the first and second log-space DTMs. When
M
1
and
M
2
are
composed to form
T
, the output tape of
M
1
, which is also the input tape of
M
2
, becomes
aworktapeof
T
.Since
M
1
may execute a polynomial number of steps, we cannot store all
its output before beginning the computation by
M
2
. Instead we must be more clever. We
keepthecontentsoftheworktapesofbothmachinesaswellas(andthisis whereweare
Search WWH ::
Custom Search