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

CIRCUIT VALUE
Instance: A circuit description with fixed values for its input variables and a designated
output gate.
Answer: “Yes” if the output of the circuit has value 1.

THEOREM 3.9.5 The language CIRCUIT VALUE is P -complete.
Proof To s h ow t h a t CIRCUIT VALUE is P -complete, we must show that it is in P and
that every language in P can be translated to it by a log-space program. We have already
shown the second half of the proof in Theorem 3.9.1 . We need only show the first half,
which follows from a simple analysis of the obvious program. Since a circuit is a graph of a
straight-line program, each step depends on steps that precede it. (Such a program can be
produced by a pre-order traversal of the circuit starting with its output vertex.) Now scan
the straight-line program and evaluate and store in an array the value of each step. Successive
steps access this array to find their arguments. Thus, one pass over the straight-line program
suffices to evaluate it; the evaluating program runs in linear time in the length of the circuit
description. Hence CIRCUIT VALUE is in P .

When we wish to show that a new language L 1 is P -complete, we first show that it is in
P . Then we show that every language L P can be translated to it in logarithmic space; that

is, for each string w , there is an algorithm that uses temporary space O (log

∈

) (as does the
program in Fig. 3.27 )thattranslates w into a string v such that w is in L if and only if v is
in L 1 . (This is called a log-space reduction .SeeSection 8.5 for a discussion of temporary
space.)
If we have already shown that a language L 0 is P -complete, we ask whether we can save
work by using this fact to show that another language, L 1 ,in P is P -complete. This is pos-
sible because the composition of two deterministic log-space algorithms is another log-space
algorithm, as shown in Theorem 8.8.1 .Thus,ifwecantranslate L 0 into L 1 with a log-space
algorithm, then every language in P can be translated into L 1 by a log-space reduction. (This
idea is suggested in Fig. 3.28 .) Hence, the task of showing L 1 to be P -complete is reduced
to showing that L 1 is in P and that L 0 ,whichis P -complete, can be translated to L 1 by a
log-space algorithm. Many P -complete languages are exhibited in Section 8.9 .

| w |

log-space reduction by Def. 3.9.1

L

log-space reduction

L 0

L 1

by Def. 3.9.1

Figure 3.28 A language L 0 is shown P -complete by demonstrating that L 0 is in P and that
every language L in P can be translated to it in logarithmic space. A new language L 1 is shown
P -complete by showing that it is in P and that L 0 can be translated to it in log-space. Since L can
be L 1 , L 1 can also be translated to L 0 in log-space.