Complexity Classes - Models of Computation: Exploring the Power of Computing - page 374

8.13.2 Uniform Circuits Are Equivalent to Turing Machines
We now show that the functions computed by log-space uniform families of circuits and by
polynomial-time DTMs are the same. Since the family of functions computed by one-tape
and multi-tape Turing machines are the same (see Theorem 5.2.1 ), we prove the result only
for the standard one-tape Turing machine and proper resource functions (see Section 8.3 ).

THEOREM 8.13.1 Let p ( n ) be a polynomial and a proper function. Then every total function
f : B ∗ →B ∗ computed by a DTM in time p ( n ) on inputs of length n can be computed by a

log-space uniform circuit family

C .

B ∗ →
B ∗ computed by a DTM M in time p ( n ) . It follows that the number of bits in the word
f n ( w ) is at most p ( n ) . Since the function computed by a circuit has a fixed-length output
and the length of f n ( w ) may vary for different inputs w of length n , we show how to create
aDTM M ∗ , a modified version of M ,thatcomputes f n , a function that contains all the
information in the function f n . The value of f n has at most 2 p ( n ) bits on inputs of length
n . We show that M ∗ produces its output in time O ( p 2 ( n )) .
Let M ∗ place a mark in the 2 p ( n ) th cell on its tape (a cell beyond any reached during
a computation). Let it now simulate M , which is assumed to print its output in the first
k locations on the tape, k

n

→B ∗ be the restriction to inputs of length n of the function f :

Proof Let f n :

B

p ( n ) . M ∗ now recodes and expands this binary string into a
longer string. It does so by marking k cells to right of the output string (in at most k 2 steps),
after which it writes every letter in the output string twice. That is, 0 appears as 00 and 1
as 11. Finally, the remaining 2 ( p ( n )

≤

k ) cells are filled with alternating 0s and 1s. Clearly,
the value of f n can be readily deduced from the output, but the length of the value f n

−

is the

same on all inputs of length n .
ATuringmachine M C that constructs the n th circuit from n represented in unary and a
description of M ∗ invokes a slightly revised version of the program of Fig. 3.27 to construct
the circuit computing f n . This revised circuit contains placeholders for the values of the
n letters representing the input to M . The program uses space O (log p 2 ( n )) ,whichis
logarithmic in n .

We now show that the function computed by a log-space uniform family of circuits can be
computed by a polynomial-time Turing machine.

THEOREM 8.13.2 Let C be a log-space uniform circuit family. Then there exists a polynomial-time
Tu r i n g ma c h i n e M that computes the same set of functions computed by the circuits in

C

.

Proof Let M C

C

.WedesigntheTM
M to compute the same set of functions on an input w of length n . M uses w to obtain a
unary representation for the input M C

be the log-space TM that computes the circuit family

to write down a description of the n th
circuit on its work tape. It then computes the outputs of this circuit in time quadratic in the
length of the circuit. Since the length of the circuit is a polynomial in n because the circuit
is generated by a log-space TM (see Theorem 8.5.8 ), the running time of M is polynomial
in the length of w .

.Ituses M C

These two results can be generalized to uniform circuit families and Turing machines that
use more than logarithmic space and polynomial time, respectively. (See Problem 8.32 .)