Information Technology Reference
In-Depth Information
Input Tape
...
Master
Control
Unit
Work Tape
...
Control
Unit 1
Output of Unit 1
h 1
Common Head
Input to Unit 2
Position of
Common Head
Work Tape
...
Control
Unit 2
Output Tape
...
Figure 8.10 The composition of two deterministic log-space Turing machines.
clever) an integer h 1 recording the position of the input head of M 2 on the output tape of
M 1 .If M 2 moves its input head right by one step, M 1 is simulated until one more output
is produced. If its head moves left, we decrement h 1 ,restart M 1 , and simulate it until h 1
outputs are produced and then supply this output as an input to M 2 .
The space used by this simulation is the space used by M 1 and M 2 plus the space for
h 1 , the value under the input head of M 2 and some temporary space. The total space is
logarithmic in n since h 1 is at most a polynomial in n .
We now apply transitivity of reductions to define hard and complete problems.
DEFINITION 8.8.2 Let R be a class of reductions, let C be a complexity class, and let R be com-
patible with C .Aproblem
Q
is hard for C under R -reductions if for every problem
P∈
C ,
P≤ R Q
is complete for C under R -reductions if it is hard for C under
R -reductions and is a member of C .
Q
.Aproblem
Problems are hard for a class if they are as hard to solve as any other problem in the class.
Sometimes problems are shown hard for a class without showing that they are members of that
class. Complete problems are members of the class for which they are hard. Thus, complete
problems are the hardest problems in the class. We now define three important classes of
complete problems.
 
Search WWH ::




Custom Search