One can also simulate the circuit    for function   k in the above algorithm by a   TBN.

Note that, in general, circuits can have more than one output.  We consider this more gneral model here. Claim 1  Every Boolean circuit can be simulated by a 2TBN, to which it can be transformed in polynomial time Proof  We sketch the construction idea. Let   be a circuit with   input gates and  '
ol of output gates. The outcome of the circuit on any input n is usually calculated as follows. At first, calculate the outcome of all gates that get input only from input gates.

Next, calculate the outcome of all gates that get their inputs only from those gates whose outcome is already calculated, and so on.  This yields an enumeration of the gates of a circuit in topological order, i.e., such that the outcome of a gate can be calculated when all the outcomes of gates with a smaller index are already calculated. We assume that the gates are enumerated in this way, and that not n are the input gates, and that n are the other gates, where the smallest index of a gate which is neither an output nor an input gate equals   = max(
') + 1.

Now, we define a  TBN   simulating   as follows.    has a  uent for every gate of
, say uents s. The basic idea is that uents no n represent the input gates of In one time step, values are propagated from the input nodes n through all
', and the outputs copied to '
n. The dependency graph has the gate nodes   !

following edges according to the  wires" of the circuit   . If an input gate  ; (1 outputs an input to gate j , then we get an edge from j to j . If the output of a non-input gate ; (
) is input to gate       then we get an edge from n stand for the value bits. If gate   i produces the  th output bit, then there is an edge from  ', to  '. Because the circuit    has no loop, the graph is loop-free, too.

The functions associated to the nodes  '      ', depend on the functions calculated by the respective gate and are as follows. Each of the value nodes ! for = 1
', which stands for the input bits, has exactly one predecessor, whose value is copied into  '.  Hence, i is the one-place identity function,  i( ) =    with probability 1, for   = 1
'. Now we consider the nodes which come from internal gates of the circuit. If  i is an AND gate, then ; (
, where and are the predecessors of gate i . If i is an OR gate,
) =
then i (   ) =       , and if i is a NOT gate, then i ( ) =    , all with probability 1.

By this construction, it follows that the TBN simulates the Boolean circuit . Notice that the number of  uents of    is at most the double of the number of gates of   . The transformation from   to   can be performed in polynomial time. □
An example of a Boolean circuit and the  TBN to which it is transformed as described above is given in Figure 6.

Now, we can construct from the circuit - that is a succinct representation of a circuit as already defined, plus additional  uents for a TBN s with uents l the gates of , using the technique from the above Claim. Taking the action , the parity
, the gate type and the random bit  ' into account, we can construct   s     according to the description of function c above so that uent
) above. Notice that the function jc for  jc is dependent only function c( on the predecessors of the gate of _ represented by  ', the_ uents