Information Technology Reference
In-Depth Information
follows because the inputs
x
1
,
x
2
,
...
,
x
T
that would be given to the FSM over time can be
given simultaneously to this circuit and it will produce the
T
outputs that would be produced
by the FSM. This circuit has
T
C
(
L
)
gates, where
C
(
L
)
is the actual or equivalent number of
gates used to realize
L
. (The circuit
L
may be realized with a technology that does not formally
use gates.) Since this circuit is not necessarily the smallest circuit for the function
f
,wehave
the following inequality, where
C
(
f
)
is the size of the smallest circuit for
f
:
·
C
(
f
)
≤
T
·
C
(
L
)
This result is important because it imposes a constraint on every computation done by a
sequential machine. This inequality has two interpretations. First, if the product
T
C
(
L
)
(the
equivalent number of logic operations employed
) of the number of time steps
T
and
the equivalent number of logic operations
C
(
L
)
per step is too small, namely, less than
C
(
f
)
,
the FSM cannot compute function
f
because the above inequality would be violated. This is
aformof
impossibility theorem for bounded computations.
Second, a complex function,
one for which
C
(
f
)
is large, requires a large value for the product
T
·
·
C
(
L
)
.Inlightofthefirst
interpretation of
T
·
C
(
L
)
as the equivalent number of logic operations employed, it makes
sense to call
W
=
T
C
(
L
)
the
computational work
done by the FSM to compute
f
.
The above computational inequality can be specialized to the bounded-memory RAMwith
S
bits of memory. When
S
is large, as it usually is,
C
(
L
)
for the RAM is proportional to
S
.As
a consequence, for the RAM we have the following computational inequality for some positive
constant
κ
:
·
C
(
f
)
≤
κST
This inequality shows the central role of circuit complexity in theoretical computer science. It
also demonstrates that the space-time product,
ST
, is an important measure of the complexity
of a problem. Functions with large circuit size can be computed by a RAM only if it either has
a large storage capacity or executes many time steps or both. Similar results exist for the Turing
machine.
1.5.2 Tradeoffs in Space, Time, and I/O Operations
Computational inequalities of the kind sketched above are important but often difficult to
apply because it is hard to show that functions have a large circuit size. For this reason space-
time tradeoffs have been studied under the assumption that the type of algorithm or program
allowed is restricted. For example, if only straight-line programs are considered, then the
pebble
game
sketched below and discussed in detail in Chapter
10
can be used to derive tradeoff
inequalities.
The standard
pebble game
is played on a directed acyclic graph (DAG), the graph of a
straight-line program. The input vertices of a DAG have no edges directed into them. Output
vertices have no edges directed away from them. Internal vertices are non-input vertices. A
predecessor of a vertex
v
is a vertex
u
that has an edge directed to
v
. The pebble game is played
with pebbles that are placed on vertices according to the following rules:
•
Initially no vertices carry pebbles.
•
A pebble can be placed on an input vertex at any time.
Search WWH ::
Custom Search