Information Technology Reference
In-Depth Information
for
i
:= 0
to
n
1
READ VALUE
(
w
i
)
WRITE INPUT
(
i
,
w
i
)
for
j
:=
n
to
m
−
1
WRITE INPUT
(
j
,
β
)
for
t
:= 1
to
T
WRITE CONTROL UNIT
(
t
,
c
t
)
WRITE OR
(
t
,
m
)
for
j
:= 0
to
m
−
−
1
WRITE CELL CIRCUIT
(
j
,
t
)
Figure 3.27
Aprogram
C
M
,
T
that simulates
T
steps of a
nondeterministic Turing machine
M
and uses
m
memory words. It reads the
n
inputs supplied
to
M
, after which it writes the input steps of a straight-line program that reads these
n
inputs as
well as
m − n
blanks
β
into the first copy of a tape unit. It then writes the remaining steps of a
straight-line program consisting of descriptions of the
T
copies of the control unit and the
mT
cell circuits simulating the
T
copies of the tape unit.
P
to write the description of a circuit
the input tape of
T
, after which it writes a fragment of a straight-line program containing the
value of
w
i
. The second loop sets the remaining initial values of cells to the blank symbol
β
.
The third outer loop writes a straight-line program for the control unit using the procedure
WRITE CONTROL UNIT
that has as arguments
t
, the index of the current time step, and
c
t
,
the tuple of Boolean choice input variables for the
t
th step. These choice variables are not used
if
M
is deterministic. In addition, this loop uses the procedure
WRITE OR
to write a straight-
line program for the vector
OR
circuitthatformsthecontents
v
t
of the cell under the head
after the
t
th step. Its inner loop uses the procedure
WRITE CELL CIRCUIT
with parameters
j
and
t
to write a straight-line program for the
j
th cell circuit in the
t
th tape.
The program
giveninFig.
3.27
is economical in its use of space and time, as we show.
Consider a language
L
in
P
;thatis,for
L
there is a deterministic Turing machine
M
L
and a
polynomial
p
(
n
)
such that on an input string
w
of length
n
,
M
L
halts in
T
=
p
(
n
)
steps.
It accepts
w
if it is in
L
and rejects it otherwise. Since
P
P
uses space logarithmic in the values
uses space logarithmic in
n
.(Forexample, f
p
(
n
)=
n
6
,
log
2
p
(
n
)=
6
log
2
n
=
O
(log
n
)
.) Such programs are called
log-space programs
.
We show in Theorem
8.8.1
that the composition of two log-space programs is a log-space
program, a non-obvious result. However, it is straightforward to show that the composition of
two polynomial-time programs is a polynomial-time program. (See Problems
3.2
and
8.19
.)
Since
of
n
and
T
and
T
=
p
(
n
)
,
P
P
P
's inner and outer loops each execute a polynomial number of steps, it follows that
is a polynomial-time program.
If
M
is nondeterministic,
P
continues to be a log-space, polynomial-time program. The
only difference is that it writes a circuit description containing references to choice variables
whose values are not specified in advance. We state these observations in the form of a theorem.
THEOREM
3.9.3
Let
L ∈
P
(
L ∈
NP
). Then for each string
w
∈
Γ
∗
a deterministic (nondeter-
ministic) circuit
C
M
,
T
can be constructed by a program in logarithmic space and polynomial time
in
n
=
C
M
,
T
, the value in the first tape cell, is (can
be) assigned value 1 (for some values of the choice inputs) if
w
|
w
|
,thelengthof
w
, such that the output of
∈
L
and
0
if
w
∈
L
.
Search WWH ::
Custom Search