Information Technology Reference
In-Depth Information
For nondeterministic computations, the circuit simulation produces an instance of an
NP
-
complete problem, a hardest problem to solve in
NP
.Here
NP
is the class of languages accepted
in polynomial time by a nondeterministic Turing machine. A first
NP
-complete problem is
stated in the following section. This topic is studied in detail in Section
8.10
.
THEOREM
3.9.1
Any computation performed by a one-tape Turing machine
M
, deterministic or
nondeterministic, on an input string
w
in
T
steps using
mb
-bit memory cells can be simulated
by a circuit
C
M
,
T
over the standard complete basis
Ω
of size and depth
O
(
ST
)
and
O
(
T
log
S
)
,
respectively, where
S
=
mb
is the storage capacity in bits of
M
's tape. For the deterministic TM
the inputs to this circuit consist of the values of
w
. For the nondeterministic TM the inputs consist
of
w
and the Boolean choice input variables whose values are not set in advance.
Proof
To construct a circuit
C
M
,
T
simulating
T
steps by
M
is straightforward because
M
is a finite-state machine now that its storage capacity is limited. We need only extend the
construction of Section
3.1.1
and construct a circuit for the next-state and output functions
C
1
(
m
)
C
T
(
m
)
0
0
a
m−
1,0
a
m−
1,
T−
1
a
m
−
1,1
a
m−
1,
T
s
m
−
1,1
s
m−
1,0
s
m−
1,
T−
1
s
m−
1,
T
C
m−
1,1
C
m−
1,
T
v
m
−
1,1
v
m
−
1,
T
s
m−
2,0
s
m−
2,
T−
1
s
j
+
1,
T−
1
a
j
,
T−
1
s
j
,
T−
1
s
j
+
1,0
a
j
,0
a
j
,1
a
j
,
T
s
j
,
T
v
j
,
T
s
j
,1
s
j
,0
C
j
,1
C
j
,
T
v
j
,1
s
j−
1,0
s
j−
1,
T−
1
s
1,
T−
1
a
0,
T−
1
s
0,
T−
1
0
s
1,0
a
0,0
a
0
,
1
a
0,
T
s
0,0
s
s
0,
T
C
0,1
C
0,
T
0,1
0
v
0,1
v
0,
T
v
0
v
T−
1
w
1
w
2
w
T−
1
v
T
h
2
h
1
h
T
v
1
Control
Circuit
Control
Circuit
Control
Circuit
q
0
c
2
q
T−
1
c
1
q
1
c
T
q
T
c
T
Figure 3.25
The circuit
C
M
,
T
simulates an
m
-cell,
T
-step computation by a nondeterministic
Turing machine
M
.Itcontains
T
copies of
M
's control unit circuit and
T
column circuits,
C
t
,
each containing cell circuits
C
j
,
t
,0
≤ j ≤ m−
≤ t ≤ T
, simulating the
j
th tape cell on the
1, 1
t
th time step.
q
t
and
a
j
,
t
is the value in the
j
th cell on the
t
th step,
s
j
,
t
is 1 if the head is over cell
j
at the
t
th time step, and
v
j
,
t
is
a
j
,
t
if
s
j
,
t
=
1and
0
otherwise.
v
t
,thevector
OR
of
v
j
,
t
,0
≤ j ≤ m −
1, supplies the
value under the head to the control unit, which computes head movement commands,
h
t
,and
a new word,
w
t
, for the current cell in the next simulated time step. The value of the function
computed by
M
resides on its tape after the
T
th step.
c
t
are
M
's s t a t e on the
t
th step and its
t
th set of choice variables. Also,
Search WWH ::
Custom Search