数理解析研究所講究録1093 巻 1999 年 99-104

99

可変マージ関数の否定数限定複雑さ
佐藤貴之
Takayuki Sato
仙台電波工業高等専門学校$\mathrm{t}\mathrm{a}\mathrm{k}\mathrm{a}\mathrm{Q}\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{o}.\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{a}\mathrm{i}^{-_{\mathrm{c}\mathrm{t}.\mathrm{a}\mathrm{C}\cdot \mathrm{j}\mathrm{P}}}$

1

天野 -幸
丸岡章
Kazuyuki Amano
Akira Maruoka
東北大学大学院情報科学研究科$\{\mathrm{a}\mathrm{m}\mathrm{a}^{1\mathrm{k}}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{U}\mathrm{O}\mathrm{a}\}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{u}\mathrm{o}\mathrm{k}\mathrm{a}.\mathrm{e}\mathrm{C}\mathrm{e}i.\mathrm{t}\mathrm{o}\mathrm{h}\mathrm{o}\mathrm{k}\mathrm{u}.\mathrm{a}\mathrm{C}.\mathrm{j}\mathrm{p}$

はじめに

.

問題は, 理論計算機科学の分野において解決しなければならない最重要な未解決問題である. この問
題を論理回路という計算モデル上で考えたとき,は,に属するクリーク関数を否定ゲートを用いない単調論理回路で計算するには, 多項式より多いゲート数が必要であることを示した. しかし, 否定ゲー
トを含む–般の論理回路において, ある関数を計算するのに多項式より多いゲート数が必要であることを示す糸
口が全くつかめない状態であることは今も変わらない.
そこで, 一般の論理回路について. NP 問題を解決する為, 直接的に否定ゲートに制限を加えない論理回路を考えるのではなく, 否定ゲートの個数を制限したときの論理回路に関する研究を行い, その時の計算量や振る舞いなどを解析した後一般の論理回路について考察するという動きがおこり, 田中と西野らは, 与えられた 変数論理関数を計算する NOT ゲートの使用を個に制限した論理回路は NOT ゲートを無制限に許した同じ関数を計算する論理回路のサイズの 2 倍と $O(n\log n)$ を加えたサイズで計算可能であることを示した. これは, 一般の論理回路における計算量を解析する時, NOT ゲートの個数をほぼ $\log n$ 個に制限した論理回路の計算量を解析すれば良いということを意味している. この結果の証明の主要な部分は, 入力列が与えられた時, これらの否定奮 1, . . . , 妬を出力する反転器を NOT ゲートの個数を $\log n$ 個に制限して $O(n\log n)$
サイズで構成した点である. 彼らの構成した回路は, 入力をソートする単調論理回路, ソート済みの列を反転す
る否定ゲートを用いた回路, ここで得られた列をもとの入力の否定列に正しく並べかえる単調論理回路の 3 つの部分よりなっている. ここで, もし, NOT ゲートの使用を $\log n$ 個に制限した時に, ソート関数を計算するサイズが $o(n\log n)$ の論理回路が存在するならば, より小さなサイズの反転器の構成につながる可能性が高いと考え$\mathrm{P}\mathrm{v}\mathrm{s}$$\mathrm{N}\mathrm{P}$$\mathrm{R}\mathrm{a}\mathrm{z}\mathrm{b}\mathrm{o}\mathrm{r}\mathrm{o}\mathrm{v}[\mathrm{R}\mathrm{a}\mathrm{z}]$$\mathrm{N}\mathrm{P}$$\mathrm{P}\mathrm{v}\mathrm{s}$$[\mathrm{T}\mathrm{N}],[\mathrm{B}\mathrm{N}\mathrm{T}]$$n$$\lceil\log 2(n+1)\rceil$$x_{1},$$\ldots,$$x_{n}$

られる.

ソート関数とそれに類似するマージ関数における結果として, マージ関数については,が, 単調論理回路でマージ関数を計算するのに $\Omega(n\log n)$ 個のゲートが必要である事を示し, ソート関数の NOT ゲー
トを制限しない場合については, Muller とが, 一般の論理回路で $O(n)$ 個の jl‘- トでソート関数が計算可能であることを示した. この事からソート関数やマージ関数は否定ゲートを含まない単調論理回路と否定ゲートを含む–般の論理回路では回路計算量が異なることがわかっている. したがって, ソート関数やマージ関数を, 制限された個数の否定ゲートを用いた回路で実現するのに必要なサイズを考えることは, 否定ゲートの効果を考える上でそれ自身非常に興味深い.
そこで, 本稿ではソート関数の否定数限定複雑さについて取り上げる. 佐藤, 天野と丸岡 [SAM] は, $O(\log n)$個に制限したとき, 入力を -tonic 列に制限したソート関数 (これを k- ソート関数と呼ぶ) は線形サイズの論理回路で計算できることを示した. さらに, 垂井 [Tar] の問題提示により, 本稿では否定ゲートの個数を $O(\log\log n)$個に制限した島ソート関数について解析することにし, 否定ゲートの個数を $O(\log\log n)$ に制限したとき, 入力
系列に同様の制限を加えることによって, 線形サイズで計算可能である事を示した.
本稿では k- ソート関数を計算する論理回路を構成する為に, 入力系列の 1 の個数の 2 進数表現の上位 $\log\log n$ 桁とその $\log\log n$ 桁では取りきれないビット 1 を含む長さの 01 系列を出力させるカウンターを構成し,Mullerと Preparata のデコーダーを $\log\log n$ 桁入力に適したものに構成し直した. カウンターの構成にあたり, 入力系列
をいくつかのブロックに分割し,1 の個数を数えることが可能なブロックを選び 1 の個数の 2 進数表現を正しく出力しながら 1 プロックずつ減らしていくという方針を取ることとした. 本稿の構成は以下の通りである. まず第2 章で基本的な定義を述べ, 第 3 章において $k-$ ソート関数の定義を述べ, その上界を与える. 第 4 章では, それから導かれる系などについて述べる.
$\mathrm{I}_{\mathrm{J}}\mathrm{a}\mathrm{m}\mathrm{a}\mathrm{g}\mathrm{n}\mathrm{a}[\mathrm{L}\mathrm{a}\mathrm{m}]$$\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{a}[\mathrm{M}\mathrm{P}]$$k$$\frac{n}{\log n}$2

諸定義

入力端子に変数, または, 定数が割り当てられた, 2 入力 AND ゲート, 2 入力 OR ゲート, NOT ゲートからなる非周期的な回路を論理回路という. NOT ゲートが現れない論理回路を, 特に, 単調論理回路という.

100

と書く.
変数論理関数 $f$ : $\{0,1\}^{n}arrow\{0,1\}$ が, 任意の $w\leq w’$ なる $w,$ $w’\in\{0,1\}^{n}$ に対して $f(w)\leq f(w’)$ を満たしているとき, $f$ を単調論理関数という. 任意の単調論理関数は単調論理回路で計算可能であり, かつ, 単調論理回路でと計算可能な関数は単調論理関数のみである. 論理回路 $C$ に含まれるゲートの個数を C のサイズといい,と表表す. 論理関数 $f$ に対して, $f$ を計算する最小のゲート数の論理回路のゲート数を f の複雑さといい,$w=\{w_{1}, \ldots, w_{n}\},$ $w’=\{w_{1}’, \ldots, w_{n}’\}$

に対し, 任意の $i=1,$$\ldots,$$n$

で $w_{i}\leq w_{i}’$ が成立するとき $w\leq w’$$n$$\mathrm{s}\mathrm{i}_{\mathrm{Z}}\mathrm{e}(C)$$\mathrm{S}\mathrm{i}\mathrm{Z}\mathrm{e}(f)$す. また, 単調論理関数 $f$ に対して, $f$ を計算する最小のゲート数の単調論理回路のゲート数を の単調複雑さとトを高々 個しか含まない論理回路のうち.
いい, sizemon $(f)$ と表す. 正整数 と論理関数 $f$ に対して, NOT
限定複雑さ, あるいは単に否定限定複雑さといい,$f$ を計算するもので最小サイズのもののゲート数を f の否定と表す. ただし, f が否定ゲート数 耕以下の論理回路では計算不能の場合には, この値は定義されない(よは のビット長 (この場合は である) を,に対して,ものとする. $0,1$ 系列
$f$

$t$

$\mathit{5}^{s^{\backslash }}-$

$t$

$t$

$t$

$\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}_{t}(f)$$|u|$$u=u_{1}u_{2}\cdots u_{\mathrm{f}}$$(u_{1}u_{2}\cdots u_{t})$

$t$

$u$

$u$

を 2 進数として見た時の値, すなわち $u_{1}2^{t-1}+u_{2}2^{t-2}+\cdots+u_{t}$ を表すものとする. 本論文で用いる対数 log の底は全て 2 である.

3

$k-$

31

ソート関数を計算する論理回路の設計
$k-$

ソート関数

k- ソート関数は入力を -tonic 列に制限したソート関数である. -tonic 列は変極点の個数により定義する.
$k$

$k$

定義 1(変極点)に変わる場所を変極の各ビットを先頭から順に見たとき,から 1, または 1 からと$x\in\{0,1\}^{n}$の1 の個数を
を$x\in\{0,1\}^{n}$-tonic 列と呼ぶ.
点という. 変極点の個数が高々 個の列と書く.
に含まれる変極点の個数を
書き,
において

$x\in\{0,1\}^{n}$

$0$

$0$

$x$

$\#_{1}(x)$

$k$

$k$

$\#\mathrm{r}(x)$$x$関数である. $k-$ ソート関数と本稿で取りあげるのは, ソート関数に新たに -tonic 列の概念を導入した -‘ノは, 入力が k-tonic 列の時に限り, 入力の列を降順にソートして出力する関数である. 厳密に定義すると, 以下の通
りである.
$k$

$k$

$-\text{ト}$定義 2(トソート関数)$SORT_{n}k$ : $\{0,1\}^{n}arrow\{0,1\}^{n}$

:
:

入力
出力
入力
なる関数を
$x_{1},$$y_{1},$$x_{1},$$\ldots,$$y_{n}$$x_{n}$$k$.

の並べかえで, $y_{1}\geq\cdots\geq$ 除を満たす.
が -tonic を満たさないときは, 出力に何の条件も課さない.
-ソート関数と呼ぶ.

$\ldots,$$\ldots,$$x_{n}$

は$x_{1},$$\ldots,$$x_{n}$

が k-tonic のとき,

$x_{1},$$\ldots,$$x_{n}$$k$

本稿の主定理は以下の通りである.
定理 1 定数$c$が存在して,$size_{kC}2$

loglog $n(SORT_{n}^{k})=o(k^{2}n)$.

を計算する論理回路を図 1 の様に構成する.
を COUNT に与える. この回路では に含まれる1 の個数を数えて,1 の個数の 2 進数表現の上位 $(\log\log n+\log k)$
桁の列 と, その 2 進数表現で取りきれなかった 1 を含む長さの 01 系列 を出力する. 次に,COUNTnk の出力を, Mullerとの手法の様に直接デコーダーに接続する事はに入力し 1の出力 と を出来ないため, 一旦
ビットの列の個数の 2 進数表現の上位 $\log\log n$ 桁 と長さに調整する必要がある. そして,REGnk の出力 と をに入力することによって, ソート済みの出力列 を生成することができる.
以下混同の恐れの無い場合には, 論理関数とこれを計算する回$REG_{n}nk,$ $DEcoDE_{n}$路を同じ記号で表す. 図 1 中の $COUN\tau^{k},$の厳密な定義は以下の通りである.

口$SORT_{n}k$

まず入力列

$x$

$x$

$u$

$\frac{n}{\log n}$$s$$\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{a}[\mathrm{M}\mathrm{P}]$$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}_{n}^{k}$$u$$\mathrm{R}\mathrm{E}\mathrm{G}_{n}^{k}$

$s$

$v$

$\frac{n}{\log n}$

$t$

$v$

$y$

$t$

$\mathrm{D}\mathrm{E}\mathrm{C}\mathrm{O}\mathrm{D}\mathrm{E}_{n}$

$j$

’

...

$q’-$

101

) -tonic
Input :
Outputs : 長さ
のビット列
begin
$\text{長さ}n\mathit{0}$$k$$F^{1}\mathrm{J}x$$\frac{n}{\log n}$$s$と, 長さ log log $n+\log$ k のビット列$u$$u=0:X^{1}=X$ :for $i:=1$ to log log do begin
COUNT;$u=u+2^{1-i}C^{i}$ ;end$s=x$ log log $n+1$ ;$n$$(X^{i})$

end.

図 2:

$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}_{n}^{k}$を計算するアルゴリズム

定義 3( カウント関数)$k$

COUNT: :入力 :出力 :が k-tonic のとき, 出力列$\{0,1\}^{n}arrow\{0,1\}^{\frac{n}{\mathrm{l}\circ \mathrm{g}n}+n+k}\log\log\log$$x=x_{1},$ $\ldots,$ $xn$$x$$\#_{1}(s)+(u_{1}u2\ldots u\log\log n+\log k0\cdots 0)$

この関数を

$k$

$s$

と 2 進表現された $0,1$ 系列 $u=u_{1},$は, $\#_{1}(x)=$が -tonic でないときは出力を制限しない.
$\ldots,$を満たす. ただし,

$u_{\log \mathrm{g}}\mathrm{l}\mathrm{o}n$

$k$

$x$

カウント関数といい, この関数を計算する論理回路をカウンターと呼ぶ.

定義 4( レギュレート関数):$k$$REG_{n}^{k}$$\{0,1\}^{\frac{n}{\log n}++k}\log\log n\logarrow\{0,1\}\frac{\circ \mathfrak{n}n}{\mathrm{g}}+\log\log n$::の $0,1$ 系列
入力 長さと, 長さ $\log\log n+\log k$ の $0,1$ 系列の出力
長さ$0,1$ 系列と, 長さ $\log\log n$ の $0,1$ 系列
ただし,, かつ, #1 $(t)+$ (Vloglog $n0\cdots 0$ ) $=\# 1(S)+(u_{1}u_{2}\cdots u\log\log n+\log k0\cdots 0)$ を満たす.
この関数を レギュレート関数といい, この関数を計算する論理回路をレギュレーターという.
$s$$\frac{n}{\log n}$

$u$

$t$

$\frac{n}{\log n}$$v$$t\in 1^{*}0^{*}$$v_{1}v_{2}\cdots$$k$

定義 5(デコード関数)$DECODE_{n}$:::$\{0,1\}\frac{n}{1\circ \mathrm{g}n}+\log\log narrow\{0,1\}^{n}$

入力 長さの列 $t\in 1^{*}0^{*}$ と $v=v_{1},$, Vloglog
は $y_{1}\geq\cdots\geq y_{n}$ を満たし, かつ, $\#_{1}(t)+$ (出力 $y=y_{1},$ $y2,$
Vloglog $n0\cdots 0$ ) $=\# 1(y)$ を満たす.
この関数をデコード関数といい, デコード関数を計算する論理回路をデコーダーと呼ぶ.

3.2
$k$

$\frac{n}{\log n}$$v_{2},$$\ldots,$$\ldots$$n$$y_{n}$$v_{1}v_{2}\ldots$

カウンターの設計
カウント関数については以下が成立する.

定理 2

$C$

:定数が存在して$\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}_{k^{2}c}$log log $n^{(co}UNT_{n^{k}}$ ) $=O(k^{2}n)$.

$\ovalbox{\tt\small REJECT}$

証明 (概略)を計算するアルゴリズムを図 2 から図 4 に示す. 定理の条件を満たす論理回路は, このアルゴリズム
を自然な形で論理回路上に実装することにより得られる.
(図 2) を計算するには COUNT (図 3) を log log 回再帰的に計算する. COUNT の出力列の長さは
入力列の長さの半分になることに留意すると, 最終的に ]$\circ \mathrm{g}\mathrm{l}\circ \mathrm{g}n$ となりこれが定義 3 中の にあたる. その COUNT で得られた桁の 1 の個数の 2 進表現を 1 桁ずっずらして加え, 出力したビットの列が となる.
はその内部で(図 4) を k 回実行する. ここでを計算するとき求めるの状態によっての出力列も異なってくる. COUNT:の入力列の長さを として,]とは, 長さ$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}_{n}^{k}$$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}_{n}^{k}$

$n$

$s$

$1\circ \mathrm{g}k+1$$\iota\circ \mathrm{g}1\circ \mathrm{g}n+1\circ \mathrm{g}k$$\mathrm{C}O\mathrm{U}\mathrm{N}\mathrm{T}^{i,j}$$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\dot{T}$$u$$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}^{i,j}$$\mathrm{E}\mathrm{x}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}^{:,j}$$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}^{\dot{*}}$$\mathrm{N}$$\mathrm{E}\mathrm{x}\mathrm{i}8\mathrm{t}\mathrm{C}$$\mathrm{e}\mathrm{a}\mathrm{n}^{i}’ j$102

Input : 長さ
Outputs: 長さの $k$ -tonic 列$n/2^{\dot{\iota}-1}$$n/2^{i}$ただし,$x^{i}$の k-tonic 列 $x^{i+1}$ と,長さ $\log k+1$ の列$\#_{1}(x^{i})=\# 1(x^{i}+1)+(c^{i}0\cdots 0)$

procedure COUNT
begin$c^{i}$.

$(x^{i})$;do begin$c^{i}=0;x^{i,1}=X^{\cdot}$$|$

for $j:=1$ to$k$;then begin
if $j=k$ then begin$x^{i+1}=P$ ;$c^{i_{=}}CP^{k}+1$;
endelse $x^{i,j+1}=P$ ;$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}^{i}\dot{\theta}(x^{i}’ j, CP^{j})$if$\mathrm{E}\mathrm{x}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{C}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}^{i,j}=1$

endelse begin$x^{i+1}=Q$ ;$c^{i}=cQ$ ;return;

end
end

end.
図 3: COUNT を計算するアルゴリズムのブロックに分割した時, 先頭の k 個のブロックの中の変極点があるかを調べる関数である.
であれば (入力が -tonic 列であることより)
であれば変極点が 1 つもないブロックが存在し,分割した全てのブロックの変極点の個数が高々1 個であること (この列を bitonic 列を呼ぶ) が容易にわかる. しかの時は, 変極点の存在しないブロックも, この 2 つの状況以外は起こり得ないことに注意する.
を入力列から削除し, その代わり入力列の 1 の個数を保存するため 1 ビット用意し, それを 1 の個数の 2 進数表現にあたる に加える. 削除後の列が図 3 においては にあたる. よって 1 の個数を正しく保存しながら入力列の長さを減らしていく事が可能となる. それを高々 回帰納的に繰り返すことにより合計 k ブロックを削除することができるので入力系列の長さを COUNT の入力の半分の長さにして出力することができる.
またの時は,bitonic selection を実行する. bitonic selection とは, 長さ 2l の列 $Z=Z_{1},$とについてを比較し大きい方のビットを左に置くように交換することをいう. bitonic
に対し, $a=1,$
selection の性質として,z が bitonic 列のとき, に bitonic selection を実行した列を と置くと, z’ の左半分が 1 かまたは〆の右半分が になることがわかる. すなわち各ブロックが bitonic 列のときは bitonic selection を行うことでブロックの左半分か右半分を 1 の個数を保存しながら削除することが可能であることを意味する. その各ブである. また
ロツクの 1 の個数を保存する為に準備したビットを全て加えることによって得られた数が図 3 の各ブロックが全て半分の長さまで削除することが出来るから–気に削除を COUNT の入力の半分の長さまで行った列が図 3 においてはに相当する. .
図 2 から 4 までを論理回路で実現した時, NOT ゲートは図 2 中の の $\log\log n$ 回の計算, 図 3 中の Clean $i,j$ の$k^{2}\log\log n$ 回の計算, 図 4 の OPEA を実行するか OPEB を実行するかの $k^{2}\log\log n$ 回の分岐,OPEA,OPEB においてのブロックの削除, カウンタの計算 (共に回) で使用されている. このゲート数を合計するとで使用されている NOT ゲートの個数は $O(k^{2}\log\log n)$ であることがわかる. また, 合計のゲートの個数も $O(k^{2}n)$ であることがわかる$\mathrm{E}\mathrm{x}\mathrm{i}\mathrm{S}\mathrm{t}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}^{i}’ j=1$$\text{を}\frac{N}{2k}$$k$$\mathrm{E}\mathrm{x}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{C}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}^{i}’ j=0$$\mathrm{E}\mathrm{x}\mathrm{i}\mathrm{S}\mathrm{t}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}^{i}’ j=1$$\mathrm{c}^{i}$$\mathrm{P}$$k$$\mathrm{E}\mathrm{x}\mathrm{i}\mathrm{S}\mathrm{t}\mathrm{C}\iota \mathrm{e}\mathrm{a}\mathrm{n}^{i}’ j=0$$\ldots,$$l$$z_{a}$$\ldots,$$Z_{2l}$$z_{a+l}$

$z’$

$z$

$0$

$\mathrm{C}\mathrm{Q}$$\mathrm{Q}$

$u$

)

$a$

$k^{2}\log 1o\mathrm{g}n$$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}_{n}^{k}$$\square$103

Input : 長さ
Outputs : 長さの列 J も j と, 長さ $\log k+1$ ビットのカウンタ $CP^{j}$の列と, 長さ $\log k+1$ ビットのカウンタ $CP^{j+1}$の列と, 長さ $\log k+1$ ビットのカウンタ $CQ$$\frac{2k+1-\mathrm{j}}{2k}N$$2k2\exists N$

長さ$P^{\dot{\iota},j}$$Q^{i,j}$$\frac{1}{2}N$

Procedure COUNT$i,j(J^{i,j})$begin$J’=\{x^{i}1", 2j\ldots jx^{i}’-:\}n$

$J”=$

{

$x^{i,j}$;から $J’$ を除いた列};

for $a:=1$ to$k$do begin$J’(a)=\{J_{\frac{i\underline{i}a1}{2k}}N+1’\ldots, J_{\frac{i,ja}{2k}N}\}$;( $J’(a)$ の全てのビットの AND);( $J’(a)$ の全てのビットの OR);
$Clean^{i,j}’ a=(ANDi,j,aoRi,j,a=)$ ;$AND^{;,j,a}=$$OR^{i,j,a}=$end
ゐ$ExiStclean^{i}’ j=\mathrm{v}C\iota_{e}an^{i,j,a}$

;

$a=1$

if $ExiStclean^{i}’ j=1$ then OPEA $(X^{i,j}, CP^{j})$else OPEB $(x^{i,j}, CPj)$ ;end.

Procedure$\mathrm{o}\mathrm{p}\mathrm{E}\mathrm{A}(x^{i}’ j, CPj)$

begin
for $a:=1$ to

if

$k$

do beginthen begin$Clean^{i,j}’ a=1$

$P’=$

{ $J’(a)$ 以外の$P=P^{\prime_{\mathrm{o}}}J\prime\prime$

end

$J’$

};

;

$CP^{j1}+j=cP+$ (( $J’(a)$ の先頭のビット);

end
end.
procedure OPEB $(X^{i,j}, CP^{j})$begin;$Q’=\emptyset$$CQ=2CP^{j}$ ;for $a:=1$ to $2(k-j+1)$ do begin;$L(a)=$ ( $Q’(a)$ に対して bitonic selection を実行したもの);$Q’(a)= \{X, \ldots, x\frac{i,ja-1}{2k}N+1\frac{i}{}2’ N\simeq_{k}\}j$

HalfL

蓑
$(a) \wedge=x\frac{i,ja-1}{2k}N+b;\sim$

if HalfL $(a)=0$ then $Q’(a)=L(a)$ の左半分
else $Q’(a)=L(a)$ の右半分;$Q’=Q’\circ Q’(a)$ ;$CQ=CQ+\mathrm{H}\mathrm{a}\mathrm{l}\mathrm{f}^{L(a)}$

;

end
end.
図 4:

$\mathrm{C}\mathrm{O}\mathrm{U}\mathrm{N}\mathrm{T}i,j$を計算するアルゴリズム

104

表 1: SORT と MERGE のサイズの対応表
レギュレータ, デコーダーについては以下の事を容易に示すことができる.
補題 1 ある定数$c$が存在して,$\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}_{c}$loglog $n(REG_{n}^{k})=o(n)$ .

$\square$定理 3 $\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}_{mon}(DECoDEn)=o(n)$ .

$\square$

ゆえに, 定理 2,3, 補題 1 より, 定理 1 を満たす論理回路

4$\mathrm{S}\mathrm{O}\mathrm{R}\mathrm{T}_{n}^{k}$\theta s 構成できる.

おわりに
定理 1 を証明したことにより, 次の系が得られる.

系1

$k$

が定数のときある定数$\mathrm{c}$が存在して,$\mathrm{s}\mathrm{i}_{\mathrm{Z}\mathrm{e}_{\mathrm{c}}}\log\log n(SoRT_{n}^{k})=o(n)$.

口

これは NOT ゲートの個数を $O(\log\log n)$ に制限したとき, 定数-ソート関数は $O(n)$ 個のゲートで構成可能であることを意味する.

以上マージ関数とソート関数の否定数限定複雑さに関して得られた結果を表 1 に示す.

*は本稿で得られた結果である.

使用できる NOT ク-“- }, の個数を $c\log n$ 個に限定したとき, ソート関数が線形サイズで計算可能かどうかについては依然未解決である. しかし,NOT ゲートの個数の制限を佐藤, 天野と丸岡 [SAM] の結果より厳しくしたときの結果を出したことにより,NOT ゲートの個数を $c\log n$ 個に制限した時 k- ソート関数は線形サイズで計算可能か否かという問題が解決される日が近いと考えている.

謝辞
最後に, 本稿を執筆するにあたり, 貴重な御意見をくださった電気通信大学の垂井淳先生に心より感謝いたし
ます.

参考文献
[AKS] M. Ajtai, J. Kom\’os and E. Szemer\’edi, “An $O(n\log n)$ sorting network”, Proc. 15th STOC, pp. 1-9, 1983.
[BNT] R. Beals, T. Nishino and K. Tanaka, “More on the Complexity of Negation-Limited Circuits”, Proc. 27th STOC,
pp. 585-595, 1995.
[Lam] E. A. Lamagna, “The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems,Sorting,and Merging”, IEEE Trans. of Comput., Vol. C-28, No. 10, pp. 773-782, 1979.

D. E. Muller and F. P. Preparata, “Bounds to Complexities of Networks for Sorting and Switching”, J. of $ACM$,
Vol. 22, pp. 195-201, 1975.
Bounds on the Monotone Complexity of Some Boolean Functions”, Soviet Math. Dokl.,. Razborov,[Raz]
Vol. 281, pp. 798-801, 1985.
[SAM] 佐藤貴之, 天野 -幸, 丸岡章, ’ 連数限定入力に対する杏定数限定ソーティング回路”, 信学技報, COMP97-120,
Vol. 97, No. 628, 1998
the Complexity of Negation-Limited Boolean Networks”, Proc. 26th STOC, pp.
[TN] K. Tanaka and T. Nishino,
38-47, 1994.
[Tar] J. Tarui, Personal Communication, 1998.

[MP]$\mathrm{A}.\mathrm{A}$$u_{\mathrm{L}_{\mathrm{o}\mathrm{W}}}\mathrm{e}\mathrm{r}$$\alpha_{\mathrm{O}\mathrm{n}}$