数理解析研究所講究録
第 833 巻 1993 年 236-241

236

A Language Complete for the Families of
Polynomial-Size Binary Decision Diagrams
多項式サイズの二分決定グラフの族に対する完全言語
Hiroshi SAWADA

Yasuhiko TAKENAGA

矢島脩三

武永康彦

澤田宏

Shuzo YAJIMA

Faculty of Engineering, Kyoto University
京都大学工学部

1Introduction

A binary decision diagram (BDD) [1] is one of representation forms of Boolean functions.
It can represent many practical Boolean functions by feasible size and there exists a uniquecanonical form for each Boolean function. Therefore it is widely used for manipulating Booleanfunctions on computers.
A BDD represents a Boolean function. On the other hand, a family of BDD’s repIesents
a language. The class of languages accepted by families of polynomial-size BDD’s (PolyBDD)[2] can be seen as a complexity class which is computable by BDD’s of feasible size. A family
and the language $\{ww|w\in\{0,1\}^{*}\}$ are examplesof symmetric functions, the languageof elements of PolyBDD.
In this paper, we show a complete language for PolyBDD under constant-depth circuit
reducibility. It reflects the characteristics of PolyBDD and is the representative language ofPolyBDD. To clarify the relations between PolyBDD and other complexity classes, it is sufficient to clarify the relations between a complete language for PolyBDD and other complexityclasses.
This paper is organized as follows. In section 2, we define a BDD and PolyBDD. In section
3, we show a complete language for PolyBDD under constant-depth circuit reducibility. In
section 4, we conclude our discussion.
$\{0^{n}1^{n}\}$2Preliminaries

2.1

Binary Decision Diagram (BDD)

A binary decision diagram (BDD) (Figure 1) [1] which represents an n-variable Boolean func, init, edge, level, ), wheretion $f(x_{1}, \cdots, x_{n})$ is a 6-tuple ($N_{V},$ $N_{C}$$\pi$

is a set of variable nodes,
is the set of constant nodes,$init\in N_{V}$ is an initial node,edge : $N_{V}\cross\{0,1\}arrow(1V_{V}\cup N_{C})$ is a set of edges,
level : $(N_{V}\cup lV_{C})arrow\{1, \cdots, n+1\}$ is a mapping from the set of nodes to the setof levels such thatlevel(init) $=1$ ,level(v) level(edge(v, )) $(b\in\{0,1\})$ if $v\in JV_{V}$ ,level $(v)=n+1$ if $v\in 1V_{C}$ ,$\{1,\cdots, n\}arrow\{1, \cdots, n\}$ is a permutation from the set of levels of variable nodes:
to the set of indexes of variables, called a variable order.
$1V_{V}$$N_{C}=\{c_{0}, c_{1}\}$

$<$

$\pi$

$b$

237
index

level$\pi$

1$arrow$3

2$arrow$

1

3$arrow$

24

Figure 1: A BDD representing a Boolean function
Each node$v$

of a BDD represents a Boolean function(inconsistency),(tautology),$f_{c_{0}}=0$$f_{c_{1}}=1$$f_{v}=\overline{x_{\pi(level(v))}}\cdot f_{edge\langle v,0)}+x_{\pi\{level(v))}\cdot f_{edge(v,1)}$$f_{v}$$x_{1}\cdot x_{2}+x_{3}$defined as follows,

if $v\in N_{V}$ .

, init, edge, level, ) represents the Boolean function finit. A BDD is called
A BDD (reduced if there are not any node such that edge $(v, 0)=edge(v, 1)$ and any pair of nodes
such that level(v) $=level(v’),$ $edge(v, 0)=edge(v’, 0)$ and edge $(v, 1)=edge(v’, 1)$ . A reduced
BDD represents a Boolean function with a variable order is unique up to isomorphism.
$N_{V},$$JV_{C}$

$\pi$

$v,$

$v$

2.2$v’$

Family of Polynomial-Size BDD’s

A BDD is one of representation forms of Boolean functions. On the other hand, a familyof BDD’s,of BDD’s is a sequenceof BDD’s represents a language. A family, init, edge, level, ) is a BDD representing an n-variable Boolean function.
where $B_{n}=$ (of BDD’s is said to accept a language
if and only ifA family$\{B_{n}\}$$4V_{V},$ $1V_{C}$$B_{1},$ $B_{2},$$L\subseteq\{0,1\}^{*}$$\{B_{n}\}$$\forall n,$$\cdots$$\pi$$b_{1}\cdots b_{n}\in L\Leftrightarrow f_{n}(b_{1}, \cdots, b_{n})=1$, where$f_{n}$is the Boolean function which$B_{n}$represents.

We can regard a family of BDD’s as a computational model which accept a language.

Definition 1 Let PolyBDD be the class of languages which are accepted by families of BDD’s
whose size are bounded by a polynomial of the number of the variables.

$\square$In this paper, we do not consider the uniformity, the property that the function $narrow B_{n}$ iscomputable easily, of familiesof BDD’s. In order to characterize nonuniform families ofBDD’s, we use nonuniform on-line Turing machines.
A nonuniform Turing machine is a Turing machine with a two-way read-only input tape.
a two-way work tape and a two-way read-only advice tape. For an input$\{B_{n}\}$$b_{1}\cdots b_{n}(b_{1\cdot}.b_{n}\in$238:.
$NC^{2}$$1$

N $L/poly$$1$$DL/poly\backslash$

PolyBDD$|$

l-DL/poly$NC^{1}$$|$$\backslash$planar-NC1
$1$

$REG$

Figure 2: The relations among the classes$\{0,1\})$ , a nonuniform Turing machine start its computation withon the input tapeand withon the advice tape, where : $\{1, 2, \cdots\}arrow\{0,1\}^{*}$ is called an advice function.
A nonuniform on-line Turing machine is a nonuniform Turing machine whose input tape isone-way.
Let $DL/poly,$ $NL/poly$ and l-DL/poly be the class of languages accepted by logarithm-spacebounded deterministic nonuniform Turing machines with polynomial advice, logarithm-spacebounded nondeterministic nonuniform Turing machines with polynomial advice and logarithmspace bounded deterministic nonuniform on-line Turing machines with polynomial advice.
Let $NC^{k}(k=1,2, \cdots)$ be the class of languages accepted by nonuniform families of constantn-depth and polynomial-size for inputs.
fan-in logic circuits ofOn the relations between PolyBDD and other classes, the following results are obtained
l-DL/poly [3], l-DL/poly
PolyBDD $\subset DL/poly[2][4],$(Figure 2), planar-NC’$DL/poly\subseteq NL/poly\subseteq NC^{2}[5]$ , where $REG$ is the class of regular languages and planar-NC1
is the class of languages accepted by nonuniform families of constant fan-in planar circuits ofn-depth and polynomial-size for inputs.
$b_{1}\cdots b_{n}$$\alpha(n)$$\alpha$$\log^{k}$$n$$\subseteq$$NC^{1}\subseteq$$\subset$$\log$$n$3

A Complete Language for the class PolyBDD

3.1

Constant-Depth Circuit Reducibility(denote $L\leq_{cd}L_{c}$ ) if
Let $L,$. We say thatis constant-depth reducible toand only if there exists a function : $\{0,1\}^{*}arrow\{0,1\}^{*}$ computable by a family of constantfan-in logic circuits of constant-depth and polynomial-size such that for all $x\in\{0,1\}^{*},$. Note that $|f(x)|$ is bounded by a polynomial ofsince the circuits arepolynomial-size.
, we say that
For a class , if
is hard for under constant-depth circuit
reducibility. If
is hard for and $L_{c}\in C$ , we say thatis complete for . If
is complete
for and $L_{c}\in NC^{1}$ , it follows that.
$L$

$L_{c}\subseteq\{0,1\}^{*}$$L_{c}$$f$$i1^{\backslash }\in$$L\Leftrightarrow f(x)\in L_{c}$$C$$L_{c}$

$C$

$|x|$

$\forall L\in C,$$L\leq_{cd}L_{c}$$C$$L_{c}$$C$$L_{c}$$C\subseteq NC^{1}$$C$$L_{c}$

23912345$42351\{\begin{array}{lll}00 0 l000l 00000l0 000 0l00000 \end{array}\}$Figure 3: A directed graph and its adjacency matrix

3.2

A Complete Language-Topologically Arranged Deterministic
Graph Accessibility Problem

We show that Topologically Arranged Deterministic Graph Accessibility Problem (TADGAP)[6] is a complete language for PolyBDD under constant-depth circuit reducibility. Before
defining the language TADGAP, we define a directed graph and its adjacency matrix (Figure3). A directed graph is a 2-tuple (V, ), where$E$$V=\{v_{1}, \cdots, v_{|V|}\}$

is a set of nodes,
is a set of directed edges.

$E\subseteq\{(v_{i}, v_{j})|v_{i}, v_{j}\in V\}$The adjacency matrix
of a directed graph $G=(V, E)$ is a $|V|\cross|V|$ matrix and its element$(1\leq i,j\leq|V|)$ is defined as follows,$(x_{\mathfrak{i}j})$$x_{ij},$$x_{ij}=\{\begin{array}{l}0if(v_{i},v_{j})\not\in Elif(v_{i},v_{j})\in E\end{array}$

We say that there exists a path from a node
to a node
there exist nodes
such thatthat the outdegree of a nodeis the value$v_{j}\in V,$graph (V, ) is topologically sorted if for all$v_{i_{1}}$$v_{j_{1}},$$v_{j_{2}},$$\cdots,$ $v_{j_{k}}\in V$$(v_{i_{1}}, v_{j_{1}}),$$v_{i_{2}}$$(v_{j_{1}}, v_{j_{2}}),$

in a directed graph (V, ) if
. We define. We say that a directed
is satisfied.
$E$$\cdots,$$(v_{j_{k}}, v_{i_{2}})\in E$$|\{v_{j}|(v_{\mathfrak{i}}, v_{j})\in E\}$$v_{i}$$E$$(v_{\mathfrak{i}}, v_{j})\in E\Rightarrow i\leq j$$v_{i},$

Definition 2 TADGAP $=\{x_{11}x_{12}\cdots x_{1m}\cdots x_{mm}|$is the adjacency matrix of a directed graphis topologically sorted,
the outdegree of each node of is or 1,
there exists a path fromtOof$(x_{ij})$$G$such that

$G$

$G$

$v_{m}$$v_{1}$

$0$

$G$

口$\}$

Theorem 1 TADGAP is constant-depth complete for PolyBDD.
[proof] From the following tWO lemmas

口Lemma 1 $TADGAP\in$ PolyBDD[proof] We prove that TADGAPl-DL/poly ( PolyBDD). Let $M$ be a logarithm-spacebounded nonuniform on-line Turing machine with polynomial advice. We design $M$ to accept
the language TADGAP. Let the input of $M$ be $y\in\{0,1\}^{*}and/|$ is the adjacency matrix ofa directed graph . The advice of $M$ for the input of length is the value of.
can check the following three conditions using the logarithm-space since $M$ knows the valueof $m=\sqrt{n},$ )is topologically sorted, 2) the outdegrees of nodes of is or 1. 3) thereexists a path from nodetosatisfying the conditions above. TherefoIe TADGAP$DL/poly\subseteq PolyBDD$ .
$\in$

$G$

$1$

$\subseteq$$\gamma\eta=\sqrt{n}$$\uparrow\tau$

$G$

$G$

$v_{1}$$v_{n}$$\wedge’\backslash /j$$0$$\in 1-$$\square$

240
index

$\Rightarrow$$C_{1}$$b_{1^{1}}b_{1^{2}}b_{0^{3}}\in L$$(x_{ij})=[0000100100010000000000000]$$\Leftrightarrow$$\in TADGAP$

Figure 4: An example of reduction
PolyBDD,Lemma 2
TADGAP[proof] For each $L\in$ PolyBDD, we consider the familyof polynomial-size BDD’s ac$B_{n}=$, init, edge, level, )(becepting the language . Let the n-variable BDD of$v_{j}’\in(N_{V}\cup N_{C})$ such that
and
$L\leq_{cd}$$\forall L\in$$\{B_{n}\}$$L$$N_{V},$$\{B_{n}\}$$1V_{C}$$\pi$$v_{i}’,$$v_{1}’=init$,$v_{j}’=edge(v_{i}’, b)\Rightarrow i<j,$$(\forall v_{\mathfrak{i}}’, v_{j}’, \forall b\in\{0,1\})$$v_{m}’=c_{1}(m=|1V_{V}\cup 1V_{C}|)$For$B_{n}$,.

and the input $b_{1}\cdots b_{n}\in\{0,1\}^{n}$ of$B_{n}$, we consider the directed graph $G=(V, E)$(figure4), where$V=(N_{V}\cup N_{C})$such that $v;=v_{i}’(1\leq i\leq m)$ ,$E=\{(v’, edge(v’,\cdot b_{\pi\langle level\langle v’))}))|v’\in N_{V}\}$.

The directed graphhas the outdegree of or 1 and is topologically sorted. It seems to beclear that there exists a path from node toof if and only if. Hence, if we
let the adjacency matrix of be ,
$G$

$0$

$v_{1}$$G$$b_{1}\cdots b_{n}\in L\Leftrightarrow y\in$$G$$b_{1}\cdots b_{n}\in L$

TADGAP.

is bounded by a polynomial of because , the size of , is bounded by a polynomial of. An element $x_{ij}(1\leq i,j\leq m)$ of is computable by the formula

$|y|$

$n$

$v_{m}$$y$$m$$n$$B_{n}$$y$$x_{ij}=_{b\in\{0,1\}}(b_{\pi(level\langle v’))}=b\wedge v_{j}’=edge(v_{i}’, b))$Therefore$y$.

iS computable $by$ a constant-depth circuit from$b_{1}\cdot$$b_{n}$

口

241
3.3

The Relation between PolyBDD and$NC^{1}$

PolyBDD because the Boolean function of the n-th bit output of
It is known thatthe n-bit binary multiplier can not be represented by a BDD of polynomial-size whereas canbe represented by a logic circuit of logarithm-depth [7]. Here, we have a question whether
PolyBDDor not (Figure 2). From the result of theorem 1, we have the following
result.
$NC^{1}\not\subset$$\subset NC^{1}$

Corollary 1 TADGAP $\in NC^{1}\Leftrightarrow PolyBDD\subset NC^{I}$

口We conclude that the necessary and sufficient condition for $PolyBDD\subset NC^{1}$ is TADGA $P\in$. However, the following result indicate that to clarify whether $(1- DL/poly\subseteq)PolyBDD\subset$is as difficult as to clarify whether $DL/poly\subseteq NC^{1}$ , which is one of the famous openproblems.
$NC^{1}$$NC^{1}$Theorem 2 $([3])1-DL/poly\subseteq NC^{1}\Leftrightarrow DL/poly\subseteq NC^{1}$4

口Conclusion

In this paper, we show that TADGAP is a complete language for PolyBDD under constantdepth circuit reducibility and that the necessary and sufficient condition for $PolyBDD\subset NC^{1}$
is TA $DGAP\in A’C^{1}$ . However, to clarify whether PolyBDD
is as difficult as to clarity
whether $DL/poly\subseteq NC^{1}$ , one of the famous open problems.
$\subset NC^{1}$Acknowledgment
The authors would like to thank all the members of Yajima Lab. at Kyoto University for theirvaluable discussion and suggestions.

References[1] R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Tran$.
Comput., $C- 35(8):677-691$ , August 1986.
[2] N. Ishiura and S. Yajima. A class of logic functions expressible by a polynomial-size binary
decision diagram. In Proc. Synthesis and Simulation Meeting and Int. Interchange (SASIMI90). pages 48-54, October 1990.
[3] 池川将夫. 論理回路の複雑さに関する一考察. $LA$ シンポジウム, .Iuly 1989.
[4] H. Sawada, Y. Takenaga and S. Yajima. On the relations between binary decision diagrams,Turing machines and combinational logic circuits. IEICE, COMP92-66, November 1992.

[5] Allan Borodin. On relating time and space to size and depth. SIAM Journal on Computing.
$6(4):733-744$ , December 1977.
[6] J. Hartmanis and S. Mahaney. Languages simultaneously complete for one-way and twoway log-tape automata. SIAM Journal on Computing, $10(2):383-390$ , May 1981.

[7] R. E. Bryant. On the complexity of VLSI implementations and graph representationsof boolean functions
application to integer multiplication. IEEE Trans. Comput..
$40(2):205-213$ , February 1991.
$\backslash vith$