Machines with Memory - Models of Computation: Exploring the Power of Computing - page 95

the initial state and inputs to M or deleting outputs or both. We assume that every function
computed by M in T steps is a subfunction f of the function f ( T M .
The simple construction of Fig. 3.3 is the first step in deriving a space-time product in-
equality for the random-access machine in Section 3.5 and in establishing a connection be-
tween Turing time and circuit complexity in Section 3.9.2 . It is also involved in the definition
of the P -complete and NP -complete problems in Section 3.9.4 .

3.1.2 Computational Inequalities for the FSM
In this topic we model each computational task by a function that, we assume without loss
of generality, is binary. We also assume that the function f ( T )
M

Ψ T
computed in T steps by an FSM M is binary. In particular, we assume that the next-state
and output functions, δ and λ , are also binary; that is, we assume that their input, state, and
output alphabets are encoded in binary. We now derive some consequences of the fact that a
computation by an FSM can be simulated by a circuit.

Σ T : Q × → Q ×

The size C Ω f ( T M of the smallest circuit to compute the function f ( T ) is no larger than

M

thesizeofthecircuitshowninFig. 3.3 . But this circuit has size T

C Ω ( δ , λ ) ,where C Ω ( δ , λ )
is the size of the smallest circuit to compute the functions δ and λ . The depth of the shallowest
circuit for f ( T )
M

·

is no more than T

· D Ω ( δ , λ ) because the longest path through the circuit of

Fig. 3.3 has this length.
Let f be the function computed by M in T steps. Since it is a subfunction of f ( T M ,
it follows from Lemma 2.4.1 that the size of the smallest circuit for f is no larger than the
size of the circuit for f ( T )

M . Similarly, the depth of f , D Ω ( f ) , is no more than that of f ( T M .
Combining the observations of this paragraph with those of the preceding paragraph yields the
following computational inequalities. A computational inequality is an inequality relating
parameters of computation, such as time and the circuit size and depth of the next-state and
output function, to the size or depth of the smallest circuit for the function being computed.

THEOREM 3.1.1 Let f ( T M be the function computed by the FSM M =(Σ , Ψ , Q , δ , λ , s , F ) in
T steps, where δ and λ are the binary next-state and output functions of M .Thecircuitsizeand
depth over the basis Ω of any function f computed by M in T steps satisfy the following inequalities:

C Ω f ( T )

M

C Ω ( f ) ≤ ≤ TC Ω ( δ , λ )

D Ω f ( T M D Ω ( f ) ≤ ≤ TD Ω ( δ , λ )

The circuit size C Ω ( δ , λ ) and depth D Ω ( δ , λ ) of the next-state and output functions of an
FSM M are measures of its complexity, that is, of how useful they are in computing functions.
The above theorem, which says nothing about the actual technologies used to realize M ,re-
lates these two measures of the complexity of M to the complexities of the function f being
computed. This is a theorem about computational complexity, not technology.
These inequalities stipulate constraints that must hold between the time T and the circuit
size and depth of the machine M if it is used to compute the function f in T steps. Let the
product TC Ω ( δ , λ ) be defined as the equivalent number of logic operations performed by
M . The first inequality of the above theorem can be interpreted as saying that the number of
equivalent logic operations performed by an FSM to compute a function f must be at least