数理解析研究所講究録
第 1799 巻 2012 年 13-20

132011 年度冬の LA シンポジウム [2]Formula Decomposition into Ternary Majorities( 多数決 3 分木への論理式分解 )上野 賢哉 *
is the universal gate for the class of
self-dual Boolean functions. This Boolean function
Any self-dual Boolean function can be decomposedis also representable by the 3-bit majority function
into compositions of 3-bit majority functions. In
with negations. Therefore any self-dual Boolean
this paper, we define a notion of a ternary mafunction can be also decomPosed into compositions
jority formula, which is a ternary tree composedof 3-bit majority functions with negations.
of nodes labeled by abit majority functions and
Ibaraki and Kameda [5] developed a decomposileaves labeled by literals. We study their complextion theory of monotone self-dual Boolean functions
ity in terms of formula size. In particular, we provefor the data structure called coteries which realize
upper and lower bounds for ternary majority formutual exclusions in distributed systems. The themula size of the parity, majority and recursive ma- ory was further investigated for self-dual
Booleanjority functions. To prove the lower bounds, wefunctions in general by Bioch and Ibaraki [1], whoanalyze the largest separation between ternary magave the decomposition scheme of the 3-bit parjority formula size and DeMorgan formula size.
ity function into comPositions of 3-bit majority
functions. We will fully utilize this decomposition
scheme in our results.
1 Introduction
There are two kinds of formula models stud-formula (DeMorgan forA class of Boolean functions closed under com- ied in the literature,-formula (full binary bapositions is called a Boolean clone. There are sys- mula) and its extension
tematic studies on the relationshiP among Boolean sis formula). In this paper, we study a formula
clones knovn as Post’s lattice [10]. (See also a sur- model MAJ3-formula (ternary majority formula)vey [2] on Post’s lattice with its $aPPlications.$ ) Ac- besides-formula. Every node
-formula andcording to the theory of Post’s lattice, any mono- of a $MAJ$ 3-formula is labeled by the 3-bit majortone self-dual Boolean function can be decomPosed ity function while every node of a -formula and-formula is labeled by a 2-bit Boolean function.
into $comPositions$ of 3-bit $mority$ functions. In
Independently $hom$ any choice of formula modother words, the 3-bit majority function is theuniversal gate for the class of monotone self-dual els, proving formula size lower bounds is one of theBoolean functions. On the other hand, the 3-bit most important problems in computational comAplexity theory as a weaker version of the circuit
Boolean function denoted bysize lower bound problem and $P\neq$ NP. A super4 京都大学次世代研究者育成センター (白眉プロジェクト),polynomial formula size lower bound for a function
kenya@kuis.kyoto-u.ac.jp

概要$\neg x_{3})\vee(\neg x_{3}\wedge x_{1})$$U_{2}$$B_{2}$$U_{2}$$B_{2}$$U_{2}$$B_{2}$$(x_{1}\wedge\neg x_{2})\vee(\urcorner x_{2}$

14

図

$1$

: Formula Size Upper and Lower Bounds

Definitions
in some complexity class (e.g., NP) including $NC^{1}$ 2
implies a separation between the two complexity
In this section, we summarize definitions conclasses (e.g., $NC^{1}\neq$ NP). The $\infty mplexity$ classcerned with Boolean functions and formula size.
$NC^{1}$is defined in terins of logarithm circuit depth,
We assume that the readers are familiar with thewhich turns out to be equivalent to polynomial forbasics of these concepts together with the notations
mula size [12]. Therefore, the effect of the basis
and .
of $O,$
for formula complexity is also significant from theviewpoint of logical circuit design.
In this paper, we will prove the $MAJ_{3}$ -formula 2.1 Boolean Functions
size upper and lower bounds in Section 3 and 5,
In this paper, we consider the following Boolean
respectively, as summarized in Figure 1. After theThrough the paper, means the number
completion of this paper, we have noticed that the functions.
of input bits.
lower bound for the parity function is weaker than
1.33 of Chokler and Zwick [3] using the random re- Definition 2.1 (Boolean lfunctions). The parity
striction technique. Still, our lower bound method function: $\{0,1\}^{n}\mapsto\{0,1\}$ is formally definedhas merit in the sense that it can be applied for $by$
any Boolean function. To prove the lower bounds,
we will show that the largest separation between
MAJ3-formula and -formula complexity is at
most $O(n^{\log_{2}3})$ in Section 4. It can be regarded as
analogue of Pratt’s result [11], which showed the-formula complexity The majority junction MAJ2 $l+1$ : $\{0,1\}^{2l+1}\mapsto$
largest separation between-formula complexity is at most $O(n^{\log_{3}10})$ . $\{0,1\}$ on odd number of input bits is defined byandWe hope that a new technical discovery to clarify
MAJ3-formula complexity will also shed light on
resolving the stiff barrier against formula complex$0,$$\Omega,$$\omega$$\ominus$$n$$\oplus_{n}$$U_{2}$$\oplus_{n}(x_{1}, \cdots,x_{n})=\{\begin{array}{l}1 (\sum_{n^{1}}^{n}x_{i}\equiv 1:= mod 2),0 (\sum_{i=1}x_{i}\equiv 0 mod 2).\end{array}$$B_{2}$$U_{2}$$MAJ_{2l+1}(x_{1}, \cdots,x_{n})=\{\begin{array}{l}1 (\sum_{:=n^{1}}x_{i}\geq l+1)n,0 (\sum_{*=1}x_{i}\leq l).\end{array}$ity of the existing models.

15
The recursive majority function $RecMAJ_{3}^{h}$$\{0,1\}^{3^{h}}\mapsto\{0,1\}$is defined by:$RecMAJ_{3}^{h}(x_{1}, \cdots,x_{3^{h}})=$$MAJ_{3}(RecMAJ_{3}^{h-1}(x_{1}, \cdots, x_{3^{h-1}})$,$RecMAJ_{3}^{h-1}(x_{3^{h-1}+1}, \cdots, x_{2\cdot 3^{h-1}})$

If we allow and 1 in leaves along with literals, MAJ3-formulas can compute all the Booleanfunctions because MAJ3 $(x_{1}, x_{2},0)=x_{1}\wedge x_{2}$ and
MAJ3 $(x_{1}, x_{2},1)=x_{1}\vee x_{2}$ . So the -bit majority
function with and 1 can be regarded as a kindof the universal gate for all the Boolean functions.
In this sense, MAJ3-formula is yet another naturalextension of -formula like-formula. Even if
we do not allow and 1 in leaves MAJ3-formulas
can compute all the self-dual Boolean functions.
Furthermore, even if we allow only variables without negations, they can compute all the monotone
self-dual Boolean functions.
The formula size for each formula model is defined as follows. For the convenience, we will not
distinguish a Boolean function
and a formulacomputing . We should note that $L_{MAJ_{3}}(f)$ isdefined only for self-dual Boolean functions whileandare defined for all Booleanfunctions.
$0$

$0$

,

$RecMAJ_{3}^{h-1}(x_{2\cdot 3^{h-1}+1}, \cdots, x_{3^{h}}))$

wiih $RecMAJ_{3}^{1}=$ MAJ3.

$U_{2}$$B_{2}$$0$

We will define another Boolean function right before it will appear. The notions of monotone andself-dual for Boolean fUnction are defined as follows.

Definition 2.2 (Monotone and Self-Dual). For
Boolean vectors
and, we define
iffor all$i\in\{1, \cdots n\}$ .
A Boolean function
is called
monotone if
implies
for any
A Boolean function is called selfdual if
where$\tilde{x}$$(y_{1}, \cdots , y_{n})$$=$$(x_{1}, \cdots, x_{n})$$x\neg\leq\vec{y}$$\vec{y}$$=$$x_{i}\leq y_{i}$$f$$\vec{x}\leq\vec{y}$$f(\vec{x})\leq f(y\gamma$$\vec{x},\vec{y}\in\{0,1\}^{n}.$$f$$f(x_{1}, \cdots,x_{n})=\neg f(\neg x_{1}, \cdots, \neg x_{n})$denotes the negation, which flips 1 to , and1.
$0$$\neg$

$0$

to

$f$

$f$

$L_{B_{2}}(f)$$L_{U_{2}}(f)$Definition 2.4 (Formula Size). The size of a formula is its number of leaves for any formula model.
We define the $fo$ rmula size of a Boolean function $f$
2.2 Formula Size
as the size of the smallest formula computing $f$ .
In this paper, we consider the following three for- We denote the sizeof -formula, -formula andmula models. For each model, a literal means either MAJ3-fomula of a Boolean,function $f$ by
a variable or the a negated variable
for some
and $L_{MAJ_{3}}(f)$ , respectively. We will someindex . Each formula is called monotone if it does times abbreviate $L_{U_{2}}(f)$ to $L(f)$for simplicity.
not have negated variables. In the definition, theSince we consider a ternary tree, the number ofnodes and mean the logical conjunction andleaves is at most three times the number of nodes.
disjunction, respectively.
So the $MAJ$ 3-formula model with and 1 leaves is
Definition 2.3 (Formula Models). A-formula similar with a formula model with gatesandis a binary tree with leaves labeled by literals and MAJ3. While this paper focuses on the
MAJ3internal nodes labeled $by\wedge and\vee.$ A-formula formula model without and 1, it might be interis a binary tree with leaves labeled by literals and esting to ask the minimum number of and 1 ofinternal nodes labeled by any of 2-bit Boolean func- $MAJ$ 3-formula as the measure of a kind of distancetions such
MAJ3-formula is to self-dual Boolean functions for future work.
a ternary tree with leaves labeled by literals and intemal nodes labeled by MAJ3.
$U_{2}$$B_{2}$$L_{B_{2}}(f)$$x_{i}$$\neg x_{i}$$L_{IJ_{2}}(f)$$i$$\wedge$$\vee$$0$$U_{2}$$\wedge,$$\vee$$-$$B_{2}$$0$$0$$as\wedge,$$\vee and\oplus_{2}.$

$A$

16
3

Ternary Majority Formula Theorem 3.1 (See also [3]).
where $n=2l+1$ .
Size Upper Bounds$L_{MAJ_{S}}(\oplus_{2l+1})\in$$O(n^{1.7329})$

In this section, we prove MAJ3-formula size upper bounds of the parity and majority function. In
both cases, the upper bounds are shown by utilizing
the decomposition scheme of Bioch and Ibaraki [1]for the 3-bit parity function as, we consider decomposition of the $(2\alpha+1)$ . m-bit parity function into acomposition of a 3-bit parity function with a m-bit
parity function and two . m-bit parity functions
as follows.

Proof. For some constant$\alpha$$\alpha$$\oplus_{(2a+1)\cdot m}(x_{1}, \cdots,x_{(2\alpha+1)\cdot m})=$$\oplus_{3}(\oplus_{m}(x_{1}, \cdots,x_{m})$$\oplus_{3}(x_{1},x_{2},x_{3})=[1, [\overline{1},\overline{2},\overline{3}], [i, 2,3]]$,,
where we use notations $[i,j, k]=MAJ_{3}(x_{i}, x_{j}, x_{k})$,.
$i=x_{i}$ and. FYom the decomposition
is an odd integer by. We show that Here we can assume that
scheme, we obtain
increasing or decreasing it at most 1. In this case,$MAJ_{3}$ -formula complexity is intermediate between-formula complexity and -complexity for both $(2\alpha+1)\cdot m$ becomes also an odd integer if $m$ isodd.
functions.
Let $S(n)=L_{MAJ_{3}}(\oplus_{n})$ and assume
for some constants $\gamma>0$ for any odd number .
3.1 The Parity Function
By increasing the value of , the slight modificabe an odd integer can be-formula, we can construct a tion which makes
In the case offollowing
estimation of . By using. By ignored for the
2-bit parity formulaa similar construction, we can construct a $2n$-bit decomposition scheme of the 3-bit parity function,$\oplus_{\alpha\cdot m}(x_{m+1}, \cdots,x_{(\alpha+1)\cdot m})$$\oplus_{\alpha\cdot m}(x_{(\alpha+1)\cdot m+1}, \cdots,x_{(2\alpha+1)\cdot m}))$$\overline{i}=\neg x_{i}$$\alpha\cdot m$$L_{MAJ_{3}}(\oplus_{3})\leq 7$$U_{2}$$B_{2}$$S(n)\leq\beta\cdot n^{\gamma}$$n$$\beta,$$\beta$$\alpha\cdot m$$U_{2}$$(x_{1}\wedge\neg x_{2})\vee(\neg x_{1}\wedge x_{2})$$\gamma$parity fomula$S((1+2\alpha)\cdot m)$$\leq 3\cdot S(m)+2\cdot S(\alpha\cdot m)+2\cdot S(\alpha\cdot m)$$\oplus_{2n}(x_{1}, \cdots,x_{2n})=(f_{1}\wedge\neg f_{2})\vee(\neg f_{1}\wedge f_{2})$from two sorts of n-bit parity formulas
and $f_{2}=\oplus_{n}(x_{n+1}, \cdots, x_{2n})$ ingeneral. Therefore we can prove an upper boundwhere $n=2^{h}$ from a recursive inequal.
ity
In the case of MAJ3-formula, we can decompose the -bits parity function into a composition-bits parof a 3-bit parity function and three
ity functions. Thus we have a recursive inequalfrom the deity
composition scheme of the 3-bit parity function.
Solving this inequality straightforwardly, we canshow an upper bound$O(n^{1.7712})$ .
Actually we can give a better upper$f_{1}$$\leq(3+4\cdot\alpha^{\gamma})\cdot\beta\cdot n^{\gamma}$$=$$\oplus_{n}(x_{1}, \cdots, x_{n})$$L(\oplus_{n})\leq n^{2}$.

It suffices to show that the last expression. Therefore we consider
bounded bysatisfies
which
ofthe minimum value$ib$$(1+2\alpha)^{\gamma}\cdot\beta\cdot n^{\gamma}$$\gamma$$L(\oplus_{2n})\leq 4\cdot L(\oplus_{n})$$3^{h}$$3^{h-1}$$3+4\cdot\alpha^{\gamma}\leq(1+2\alpha)^{\gamma}$

from both sides. We can verify
by eliminatingthat this inequality is satisfied when $\alpha=1.73896$
and $\gamma=1.73282$ .
$\beta\cdot m^{\gamma}$$\square$$L_{MAJ_{3}}(\oplus_{3^{h}})\leq 7\cdot L_{MAJ_{8}}(\oplus_{3^{h-1}})$$L_{MAJ_{3}}(\oplus_{3^{h}})\in O(n^{\log_{3}7})\subseteq$

bound as follows.

3.2

The Majority Function

Our MAJ3-formula size upper bound for the
majority function essentially relies on the general theory established by Paterson, Pippenger and17
Zwick [8]. Their idea is based on construction of acarry save adder from a full adder of fixed size as
building blocks. Here we consider a full adder FA3
from 3 bits to 2 bits. The first and second output
bitsof FA3 are the 3-bit parity and majority
function, respectively.
In the case of-formula, the full adder FA3
can be constructed by $y_{1}=(x_{1}\wedge((\neg x_{2}\vee x_{3})\wedge$$y_{1},$$y_{2}$$U_{2}$$(x_{2}\vee\neg x_{3})))\vee(\neg x_{1}\wedge((x_{2}\wedge\neg x_{3})\vee(\neg x_{2}\wedge x_{3})))$$y_{2}=[1,2,3]$

trix is. So the corresponding occurrence ma-$M=(\begin{array}{lll}3 2 2l 1 1\end{array})\cdot \mathbb{R}om$

this, we can ob-

tain the following MAJ3-formula size upper boundfor the majority function.
Theorem 3.3. $L_{MAJ_{3}}(MAJ_{21+1})\in O(n^{3.7925})$
where $n=2l+1$ .

Proof Fortheoccurrence

matrix,

$M$

$=$

and
. They defined, the inequality
the notion of the occurrence matrix. It summarizes
the information of the number of occurrence in the which appears in the theorem of Paterson,
formula. For example, the occurrence matrix of the Pippenger and Zwick [8] can be interpreted as$y_{2}=(x_{1}\wedge x_{2})\vee((x_{1}\vee x_{2})\wedge x_{3})$$(\begin{array}{lll}3 2 21 1 1\end{array})$$\Vert\vec{x}\Vert_{\gamma}\leq\Vert M\cdot x\urcorner|_{\gamma}$$p(a, b, c,\gamma)=(3\cdot a+2\cdot b+2\cdot c)^{\gamma}+(a+b+c)^{\gamma}-$above case is$M=(\begin{array}{lll}2 4 41 2 2\end{array})$. In the first andsecond row of the matrix, each entry counts thenumber of occurrence of each variable in the firstand second formula, respectively.
From the construction of an arbitrary fixed size
full adder and its corresponding occurrence matrix,
Paterson, Pippenger and Zwick [8] gave the following general upper bound method.

Theorem 3.2 ([8]). Let $M$ be an occurrence matrx of some full adder for some fixed basis andsome Boolean function . Let
be themum value of such thatfor anyvectorwhere. Then$O(n^{\epsilon(M)+o(1)})$
gives a formula size upper bound foron the fixed basis.
$f$$\epsilon(M)$$ma\mathfrak{X}-$$\Vert x\urcorner|_{\gamma}\leq\Vert M\cdot x\urcorner|_{\urcorner}$$\frac{1}{\gamma}$$\vec{x}\geq\vec{0}$$||x \Vert_{\gamma}=(\sum_{i}|x_{i}|^{\gamma})^{1/\gamma}$$f$. If $L_{MAJ_{3}}(MAJ_{n})\in O(n^{\gamma})$ , there
exists $a,b,$ $c>0$ such that $p(a, b, c, \gamma)<0$ . We set$a=0.729608,$ $b=c=1$ and $1/\gamma=3.7925$ . Then,
we have $p(a, b, c, \gamma)\approx-0.0000256657<0$ . Thiscertifies that the maximum value of
which
satisfies
for any vectors
isless than 3.7925. Thus we have obtained the upperbound.
$a^{\gamma}-b^{\gamma}-c^{\gamma}\geq 0$$1/\gamma$$\square$

The optimality of the value can be confirmed
by numerical analysis. That is, the minimum valueof $p(a, b,c, \gamma)>0$ for $\gamma=3.7924$ .
The best monotone-formula size upper boundfor the majority function is $O(n^{5.3})$ by a probabilistic construction of Valiant [13]. Following
the analysis of Valiant‘s constmction replaced bybalanced compositions of the 3-bit majority function with random variables, we can construct amonotone MAJ3-formula whose size is $O(n^{4.2945})$$(\supseteq O(n^{\log_{3/2}}3+\log_{2}3))$ .
The size of its conversion into a monotone-formula is $O(n^{6.2913})$$(\supseteq O(n^{\log_{3/2}}5+\log_{2}5))$and larger than Valiant‘s

By the theorem, we can derive a-formula size
upper bound of $O(n^{4.70})$ . Paterson and Zwick [9]gave a construction of the full adder from 11 bits to
4 bits and an improved upper bound of $O(n^{4.57})$ .
In the case of -formula, Paterson, Pippenger
and Zwick [8] proved a-formula size upper bound.
bound of $O(n^{3.21})$ improved to $O(n^{3.13})$ by Paterson and Zwick [9].
In the case of $MAJ$ 3-formula, the full adder $FA$ 3
can be constructed byand$U_{2}$$B_{2}$$B_{2}$$y_{1}=[1, [\overline{1},\overline{2},\overline{3}], [\overline{1},2,3]]$$\vec{x}\geq\vec{0}$$\Vert\vec{x}||_{\gamma}\leq\Vert M\cdot x\urcorner|_{\gamma}$$\gamma$$U_{2}$$U_{2}$

18. At first glance, the recursive maRanslation from Ternaryjority function seems to have the largest expanMajority Formulas to De- sion factor
from a MAJ3-formula into a4$L_{MAJ_{3}}(f_{3})=a$$U_{2^{-}}$$\log_{3}5$

Morgan Formulas

formula among all the MAJ3-formulas. Surprisingly, this is not true as we prove in the next lemma.

In this section, we analyze the relation between
3-formula complexity and -formula com- Lemma 4.2. For any self-dual Boolean function ,plexity. The results in this section will be useful $L(j)\in O(L_{MAJ_{3}}(f)^{\log_{2}3})\subseteq O(L_{MAJ_{3}}(f)^{1.5850})$ .
to derive a MAJ3-formula size lower bound ffom a
Proof. We are looking for the largest formula ex-formula size lower bound for the same function-formula.
pansion $bom$ a MAJ3-formula into a
as shown in Section 5. We begin with the following
Differently from the recursive majority function,
simple proposition.
the same variable might appear more than once in a
Proposition 4.1. $L_{MAJ_{3}}(B\epsilon cMAJ_{3}^{h})=n$ where ternary majority formula for an arbitrary $Bo$ olean$n=3^{h}$ is the number-formulafunction . In this case, the expanded
of input bits.
can shrink more. So we can concentrate on the case
Proof. The upper bound $L_{MAJ_{8}}(RecMAJ_{3}^{h})\leq n$ in which all the variable appear exactly once. Thatfollows from the same construction as the definiis, $L_{MAJ_{3}}(f)=n$ .
tion. The lower bound $L_{MAJ_{3}}(RecMAJ_{3}^{h})\geq n$ is
We assume that $L(f)\leq\beta\cdot L_{MAJ_{S}}(f)^{\gamma}$ for any
also immediate because it depends on all the variself-dual Boolean function and consider an inducables.
tive argument. The expansion factor must satisfy
$MAJ$

$f$

$U_{2}$$U_{2}$$U_{2}$$U_{2}$$f$$\square$$\gamma$Rom a majority formula $L(MAJ3)\leq 5$ , we
can recursively construct a formula for the recursive majority function whose size is . There
fore we have an upper bound $L(RecMAJ_{3}^{h})\leq 5^{h}$ ,i.e., $L(RecMAJ_{3}^{h})\in O(L_{MAJ_{S}}(f)^{1.4650})$ . Similarly, the best upper bound we know for. Theformula is also $L_{B_{2}}(RecMAJ_{3}^{h})$quantum adversary bound [7], which is useful to
prove-formula size lower bounds, has a nicecomposition property written as ADV $(f\cdot g)\geq$
ADV $(f)$ . ADV $(g)$ . It implies a formula size lower
bound $4^{h}\leq L(RecMAJ_{3}^{h})$ , i.e. $L(RecMAJ_{3}^{h})\in$$5^{h}$$B_{2^{-}}$$\leq$$5^{h}$$U_{2}$$\Omega(L_{MAJ_{3}}(f)^{1.2618})$.

.

$(L_{MAJ_{3}}(f_{2}))^{\gamma}+\beta\cdot(L_{MAJ_{3}}(f_{3}))^{\gamma}\leq\beta\cdot(L_{MAJ_{3}}(f))^{\gamma}$

by looking at a formula expansion from a $MAJ3-$
into a-formulaformula $f=$ MAJ3
$f=$ $(f_{1} A f_{2})\vee((f_{1}\vee f_{2})\wedge f_{3})$ . This expansion
is processed from leaves to the root in a recursiveway.
We can assume that $L_{MAJ_{8}}(f_{1})\leq L_{MAJ_{3}}(f_{2})\leq$$L_{MAJ_{3}}(j_{3})$without loss of generality. We set$L_{MAJ_{3}}(J_{1})=a-b,$ $L_{MAJ_{3}}(f_{2})=a+b$ and$L_{MAJ_{3}}(f_{3})=a+c$ where $a>b\geq 0$ and $c\geq b\geq 0$ .
In this case, we need to find the minimum valueof which always satisfies 2 $\cdot(a-b)^{\gamma}+2\cdot(a+$$b)^{\urcorner}+(a+c)^{y}\leq(3a+c)^{\gamma}$ . So we set $p(a, b, c, \gamma)=$$(3a+c)^{\gamma}-(a+c)^{\gamma}-2\cdot(a+b)^{\gamma}-2\cdot(a-b)^{\gamma}$ and seek
the minimum value of such that $p(a, b, c, \gamma)\geq 0$
for any $a>b\geq 0$ and $c\geq b>0$ .
and and consider $q(\alpha)=$First we fix
where $\alpha=\frac{c}{a}(0<\alpha)$ . Byof $y=x^{\gamma},$the derivative$(f_{1}, f_{2},f_{3})$$U_{2}$$\gamma$

We call the value an expansion factor froma MAJ3-formula into
-formula for an arbiif $L(f)$trary self-dual Boolean function$O((L_{MAJ_{3}}(f))^{\gamma})$ . In the case of the recursive maby solving
jority function, we can prove
5.
where $L_{MAJ_{3}}(f_{1})=L_{MAJ_{3}}(f_{2})=$$\gamma$$U_{2}$$f$$\gamma\geq\log_{3}5$$a^{\gamma}\leq(3a)^{\gamma}$

an inequality$L(f)\leq 2\cdot\beta\cdot(L_{MAJ_{3}}(f_{1}))^{\gamma}+2\cdot\beta$$\in$$\gamma$

$a,$

$b$

$\gamma$$(3+\alpha)^{\gamma}-(1+\alpha)^{\gamma}$$y’=\gamma\cdot x^{\gamma-1}$$(3+\alpha)^{\gamma}$

19
increases more thanwhenever slightly
Pratt [11] proved $L_{U_{2}}(f)\in O((L_{B_{2}}(f))^{\log_{3}10})\subseteq$
increases. So
monotonically increases as in- $O((L_{B_{2}}(f))^{2.096})$ . The exponent $\log_{3}10$ is derived
creases. To minimize $p(a, b, c.\gamma)$ for fixed , we from the -formula size of 10 for the 3-bit parity
would like to minimize
and had better be function. The above lemma can be seen as an anaas small as possible. Hence we set $c=b$ because logue of Pratt’s bound [11] for the relation between$c\geq b$ .
$MAJ$ 3-formulas and-formulas.
Next we consider$3\cdot(1+a)^{\gamma}-2\cdot(1-a)^{\gamma}$ where.
Since
Ternary Majority Formulafor any $\alpha(0\leq\alpha<1)$ implies 5$p(a, b, c,\gamma)\geq 0$ for any
and , it suffices to seek
Size Lower Bounds
the minimum which satisfies this condition.
In general, we can derive a $MAJ$ 3-formula size
It is easy to see thatis not the largest expansion factor because $r(1, \log_{3}5)\approx-0.660928<$ lower bound for an arbitrary Boolean function $hom$a -formula size lower bound of the same function
while $r(1, \log 35)=0$ . On the other hand,seems to be a good candidate which is very near to using Lemma 4.2 as follows.
the largest expansion factor because $r(O, \log_{2}3)\approx$
Theorem 5.1. For any self-dual Boolean func$0.704522>0$ and $r(1,\log_{2}3)\approx 1.77636\cross 10^{-15}>$$L_{MAJ_{3}}(f)$tionsuch that $L(f)$. To confirm $r(O, \log_{2}3)\geq 0$ for $0\leq\alpha<1$ ,.
it is sufficient to draw the graph of$(0\leq\alpha<1)$ as shown in Figure 2. (Strictly speakProof. By Lemma 4.2, an upper bound for$ing$ , it requires a rigorous analysis on, formula size expanded from a MAJ3-formula ofbut we omit it in this paper.)size $N$ is at most $O(N^{\log_{2}3})$ . This size must be
not smaller than the formula size lower bound$L(f)\in\Omega(n^{c})$ . Therefore we have obtained the the$(1+\alpha)^{\gamma}$$\alpha$$q(\alpha)$$\alpha$$U_{2}$$\gamma$$q(\alpha)$$\alpha$$U_{2}$$r( \alpha, \gamma)=\frac{p(a,b,b_{\urcorner}\cdot)}{a^{\gamma}}=(3+\alpha)^{\gamma}-$$\alpha=\frac{b}{a}(0\leq\alpha<1)$$r(\alpha, \gamma)\geq 0$

$a,$

$b$

$c$

$\gamma$$\log_{3}5$$0$$U_{2}$$\log_{2}3$

$f$

$\in$

$\Omega(n^{c}),$

$\in$

$0$

$\Omega(n^{c/\log_{2}3})$$r(\alpha, \log_{2}3)$$U_{2}-$$r(\alpha, \log_{2}3)$

orem.

口

Rom
-formula size lower bounds ofand $L(MAJ_{n})\in\Omega(n^{2})$ by Khrapchenko [6],we have the following corollaries.
$L(\oplus_{n})\in$$U_{2}$$\Omega(n^{2})$Corollary 5.2. $L_{MAJ_{3}}(\oplus_{2l+1})\in\Omega(n^{1.2618})$ and$L_{MAJ_{3}}(MAJ_{2l+1})\in\Omega(n^{1.2618})$ where $n=2l+1$ .
0.2

0.4

0.6

0.8

1.0

Since $2/\log_{2}3=\log_{3}4$ , these lower bounds arequal to the-formula size lower bound for therecursive majority function accidentally. It seems$2\cdot(1-\alpha)^{Iog_{2}3}(0\leq\alpha<1)$ .
to be difficult to give a matching MAJ3-formula
く．size upper and lower bounds even for the parity
Therefore the largest expansion factor is at mostfor-formula, which is given for a MAJ3-formula with $a-$ unction while we can obtain those
tight
to
and
Both
of
them
seem
be
not
-formula.
$1=b=c$ , i.e., $L_{MAJ_{3}}(f_{1})=1$ and $L_{MAJ_{3}}(f_{2})=$aand have room for further improvements.
$L_{MAJ_{3}}(f_{3})$ for each subtree.
$U_{2}$

図 2: $r(\alpha,\log_{2}3)=(3+\alpha)^{\log_{2}3}-3\cdot(1+\alpha)^{\log_{2}3}-$

$1$

$1$

$U_{2}$$f$$\log_{2}3$$i$$\square$$B_{2}$

20
6

Concluding Remarks[6] V. M. Khrapchenko. Complexity of the realization of a linear function in the case of
circuits. Mathematical Notes, 9:21-23, 1971.

$\pi-$In this paper, we have introduced the notionof MAJ3-formula and have shown the upper andlower bounds for $MAJ_{3}$ -formula size of several
Boolean functions. MAJ3-formula can be regarded
as the most simplified form of threshold circuits aswell as neural networks. Therefore there are possibilities to utilize techniques related with them.
We hope that developing a new stream of studies

on MAJ3-formulas will contribute a new progress
revealing the complexity of itself as well as otherexisting formula models.

[7] S. Laplante, T. Lee, and M. Szegedy. The
quantum adversary method and classical formula size lower bounds. Computational Complexity, 15(2):163-196, 2006.
[8] M. S. Paterson, N. Pippenger, and U. Zwick.
Optimal carry save networks. In Boolean function complexity, volume 169 of London Mathematical Society Lecture Note Series, pages
174-201. Cambridge University Press, 1992.
[9] M. S. Paterson and U. Zwick. Shallow circuits and concise formulae for multiple addition and multiplication. Computational Complesity, $3(3):262-291$ , 1993.

参考文献[1] J. C. Bioch and T. Ibaraki. Decompositions ofpositive self-dual boolean functions. Discrete, 1995.
Mathematics, 140(1-3):[10] E. L. Post. The two-valu $ed$ iterative systems ofmathematical logic, volume 5 of Annals Math[2] E.
hler, N. Creignou, S. Reith, andematical Studies. Princeton University Press,
H. Vollmer. Playin with boolean blocks, part
1941.
I: Post’s lattice with applications to complexity theory. $ACM$ SIGACT News, $34(4):38-52$ , [11] V. R. Pratt. The effect of basis on size ofBoolean expressions. In Proceedings of the
2003.
$23\triangleleft 6$$B\ddot{o}$$g$$1\theta th$[3] H. Chockler and U. Zwick. Which bases admit

non-trivial shrinkage of formulae? Computa, 2001.
tional Complexity,

Annual Symposium on Foundations of Computer Science (FOCS 1975), pages 119-121.
IEEE, 13-15 Oct. 1975.

$10(1):28\triangleleft 0$[4] M. J. Fischer, A. R. Meyer, and M. S. Paterson. $\Omega(n\log n)$ lower bounds on length of
Boolean formulas. SIAM Joumal on Comput-

ing, 11(3)$:416\triangleleft 27$, Aug. 1982.

[5] T. Ibaraki and T. Kameda. A theory of coteries: Mutual exclusion in distributed systems. IEEE 7hansactions on Paralld and Distributed Computing, PDS-4(7):779-794, July

1993.

[12] P. Spira. On timehardware complexity tradeoffs for boolean functions. In Proceedings of the
4th Hawaii Symposium on System Sciences,pages 525-527, 1971.
[13] L. G. Valiant. Short monotone formulae forthe majority function. Joumal of Algorithms,
5(3) $:363-366$ , Sept. 1984.