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

The second log-space transformation evaluates the circuit with temporary work space
proportional to the maximal length of such strings. If the strings identifying gates have
larger length, their transformation would use more space. (Note that it is easy to identify
gates with an O (log 2 n ) -length string(s) by concatenating the number of each gate on the
path to it, including itself.) For this reason we give an efficient encoding of gate locations.
The gates of circuits in NC 1 generally have fan-out exceeding 1. That is, they have more
than one parent gate in the circuit. We describe how to identify gates with strings that may
associate multiple strings with a gate. We walk the graph, which is the circuit, starting from
the output vertex and moving toward input vertices. The output gate is identified with the
empty string string .Ifwereachagate g via a parent whose string is p , g is identified by
p 0or p 1. If the parent has only one descendant, as would be the case for NOT gates and
inputs, we represent g by p 0. If it has two descendants, as would be the case for AND and
OR ,and g has the smaller gate number, its string is p 0; otherwise it is p 1.
The algorithm to produce each of these binary strings can be executed in logarithmic
space because one need only walk each path in the circuit from the output to inputs. The
tuple defining each gate contains the gate numbers of its predecessors, O (log n ) -length
numbers, and the algorithm need only carry one such number at a time in its working mem-
ory to find the location of a predecessor gate in the input string containing the description
of the circuit.
The second log-space transformation evaluates the circuit using the binary strings de-
scribing the circuit. It visits the input vertex with the lexicographically smallest string and
determines its value. It then evaluates the gate whose string is that of the input vertex minus
the last bit. Even though it may have to revisit all gates on the path to this vertex to do this,
O (log n ) space is used. If this gate is either a) AND and the input has value 0, b) OR and
the input has value 1, or c) NOT , the value of the gate is decided. If the gate has more than
one input and its value is not decided, the other input to it is evaluated (the one with suffix
1). Because the second input to the gate is evaluated only if needed, its value determines
the value of the gate. This process is repeated at each gate in the circuit until the output
gate is reached and its value computed. Since this procedure keeps only one path of length
O (log n ) active at a time, the algorithm uses space O (log n ) .

An important open question is whether the complexity hierarchy of this theorem collapses
and, if so, where. For example, is it true that a problem in P is also in NC ?Ifso,allserial
polynomial-time problems are parallelizable with a number of processing elements polynomial
in the length of the input and poly-logarithmic time, an unlikely prospect.

8.15.2 Circuits of Polynomial Size
We now examine the class of languages P/poly and show that they are exactly the languages
recognized by Boolean circuits of polynomial size. To set the stage we introduce advice and
pairing functions.
DEFINITION 8.15.2 An advice function a : ￿ →B ∗ maps natural numbers to binary strings.

A polynomial advice function is an advice function for which

| a ( n ) |≤ p ( n ) for p ( n ) a

polynomial function in n .
DEFINITION 8.15.3 A pairing function < , > : B ∗ ×B ∗ →B ∗ encodes pairs of binary strings
x and y with two end markers and a separator (a comma) into the binary string < x , y > .