CIRCUIT COMPLEXITY と FINITE MODEL THEORY

黒田覚

1998 年 6 月 26 日東北大学に於て

1. 序

計算の理論においては, 古くから Turing 機械が計算モデルとして一般的に使われてきたが, 現在のコンピュータアーキテクチャにより近いモデルとして, 論理回路を用いたものがある.

計算量理論においても, 多項式時間計算可能なクラス P の Boolean circuit を用いた特徴づけなどの他, P より小さいクラスの階層 AC^{i} NC^{i} は回路を用いた美しい簡明な表現を持ち, その分離問題は P = NP 問題と同様, 重要な未解決問題となっている.

通常, 回路の複雑さは, 入力から出力までの距離 (depth) と, 論理素子の数 (size) で表される. これらの関係は Turing 機械における時間量と領域量の関係に似た構造を持っており, 例えば depth と size の間には trade-off が成立する. 特に, depth が入力に対して定数になるような回路については size が多項式にならないような関数の存在がしられている. (Furst-Saxe-Sipser, Håstad)

Chandra,Stockmeyer,Vishkin はこれを基に constant depth circuit による reduction を定義し, それを用いて様々な関数を分類した.

また N. Immerman は model theory を用いて, AC^{0} 等のクラスの新しい特徴づけを与え, それにより AC^{0}-reduction 等の証明が簡単になることを示した. この方法は descriptive complexity と呼ばれるが, その簡明さから近年, 様々なクラスを表現するのに有効な手段となりつつある.

ここでは, circuit complexity の基本概念からはじめて, constant depth reducibility, descriptive complexity への導入を試みる.

2. 基本概念

以下では {0, 1}^{+} は長さが 1 以上の 2 進列を表し x ∈ {0, 1}^{+} に対して |x| を x の長さとする. はじめに circuit を定義する.

定義 2.1.

(1) 入力サイズ n の circuit とはラベル付き directed acyclic graph で次を満たすものをいう.

(a) 各 node には ∨, ∧, ¬, x_{1},…, x_{n} のいずれかのラベルがついている.

(b) 各 node に入る edge と出る edge をそれぞれその node への入力, 出力という. 入力と出力の両方がある node を内部 node, 出力のみの node を入力 node, 入力のみの node を出力 node という. 内部 node と出力 node には

Typeset by AMS-TEX

∨, ∧, ¬ のいずれかのラベルがついており, 入力 node には x_{1},…, x_{n} のいずれかのラベルがついている. 入力 node 以外の node を gate という.

(c) 出力 node は 1 つのみである.

(2) ∧-gate,∨-gate への入力 edge の数をその gate の fan-in という.

(3) C を circuit とするとき,

depth(C) = max{ 入力 node x_{i} から出力 node までの距離: 1 ≤ i ≤ n}
size(C) = C の gate の個数

(4) circuit の族 {C_{1}, C_{2} … } を単に circuit と呼ぶことがある. 2 進列上の関数 f : {0, 1}^{m} → {0, 1}^{n} を circuit C = {C_{1},… C_{n}} が計算するとは, 各 1 ≤ i ≤ n に対して, f(x_{1},…, x_{m}) の i ビット目を C_{i} が計算することをいう. 関数 f : {0, 1}^{+} → {0, 1}^{+} を circuit C が計算するとは, C は f の {0, 1}^{m} への制限を計算する circuit から成ることをいう.

定義 2.2. 各 gate の fan-in に制限がない circuit を UF(unbounded fan-in) circuit といい, fan-in が k 以下のものを fan-in k circuit という.

i ≥ 0 に対して, AC^{i}(NC^{i}) は size が n^{O(1)} で depth が O((log n)^{i}) である UF(fan-in 2) circuit で計算される関数の集合とする.

命題 2.1. 各 i ≥ 0 に対して NC^{i} ⊆ AC^{i} ⊆ NC^{i+1}.

また Håstad [5] によれば

定理 2.1. AC^{0} ⊊ NC^{1}.

ところで定義 2.2 にはひとつ問題がある. すなわちいま A ⊂ ℕ を帰納的でない集合とし, f : {0, 1}^{+} → {0, 1}^{+} を

f(x) = \{ \begin{matrix}1 & if |x| ∈ A \\ 0 & if |x| ∉ A \end{matrix}

とすれば f は AC^{0} で計算できるが, 帰納的ではない. すなわち AC^{0} は帰納的でない関数を含んでしまうことになる. これを避けるために次の uniform という概念を考える.

定義 2.3. circuit の族 {C_{1}, C_{2},… } が logspace uniform とは, 入力 n に対して C_{n} を計算する logspace Turing 機械が存在することをいう.

以下では uniform とは logspace uniform のことをいい, AC^{i}, NC^{i} はすべて uniform なクラスとする.

3. Circuit Complexity と Turing 機械の Complexity

ここではよく知られている Turing 機械の complexity がどの程度の circuit complexity を持つかについて述べる.

定理 3.1. A ∈ T IME(t(n)) とすると A は O(t(n)^{2}) size の circuit で計算できる.

証明. 文献 [1],[3].

したがって多項式時間計算可能な関数のクラス P は多項式サイズの circuit で計算できる. ただしこの逆は成り立たない (なぜなら多項式サイズの circuit は nonuniform なものも含む). 多項式サイズの circuit は P/poly と呼ばれる計算量のクラスと一致することが知られている (文献 [1]). このことから P/poly は nonuniform P とも呼ばれる.

一方, depth に制限をつけると次が成り立つ.

定理 3.2. A ∈ NSP ACE(s(n)) とすると, A は O(s(n)) depth, 2^{O(s(n))} size の UF circuit で計算できる.

証明. 文献 [3].

系 3.1. LOGSP ACE ⊆ NLOGSP ACE ⊆ AC^{1}.

また NC^{1} circuit は logspace の Turing 機械で simulate できるから, AC/NC の階層に対して次が成り立つ.

AC^{0} ⊂ NC^{1} ⊆ LOSP ACE ⊆ NLOGSP ACE ⊆ AC^{1} ⊆ ⋯
4. AC^{0} 還元可能性

ここで考えている circuit complexity のクラスのうち最も弱いものは, AC^{0} である. したがって AC^{0} の circuit を使った還元可能性を考えることにより, 様々な関数の間の強さの関係を調べることができる.

定義 4.1. f, g を関数とするとき, f が g に AC^{0} reducible である (f ≤_{AC^{0}} g) とは, ∧, ∨, ¬ に g を計算する gate を加えた O(1) depth, n^{O(1)} size circuit で f が計算できることをいう.

AC^{0} reduction を使って主な関数の間の関係を調べてみると次のようになる.

定義 4.2.

Majority(x_{1},…, x_{n}) = 1 iff ∑_{i} x_{i} ≥ \frac{n}{2},

Mod_{p}(x_{1},…, x_{n}) = ∑_{i} x_{i} mod p,

BinaryCount(x_{1},…, x_{n}) = ∑_{i} x_{i}

定理 4.1.

Mod_{p} ≤_{AC^{0}} Majority ≡_{AC^{0}} BinaryCount ≡_{AC^{0}} Multiplicaion.

Håstad により Parity は AC^{0} に入らないことがわかっているからこれらを使って新しいクラスを作ることができる.

定義 4.3. ACC = {f : ∃p(f ≤_{AC^{0}} Mod_{p})}. T C^{0} = {f : f ≤_{AC^{0}} Majority}.

これらの関数の強さについては, Chandra,Stockmeyer,Vishkin [4], Smolensky [8], らによって調べられているが, ACC =?T C^{0} などは未解決問題である.

5. Descriptive Complexity

N. Immerman は有限集合上で first order formula によって定義される 2 進列の集合が uniform AC^{0} に一致することを示し, 更にこれを元にして T C^{0}, NC^{1} 等のクラスを有限集合上のモデル論を使って表現した ([2], [6], [7]). 以下でその概要を述べる.

まず, L_{1} を定数記号 c_{min}, c_{max} と関係記号≤, BIT (x, i), X(i) から成る 1 階言語とする.

定義 5.1. A ⊆ {0, 1}^{+} を 1 変数述語とするとき, A ∈ F O とは, ある L_{1} sentence θ が存在してすべての x ∈ {0, 1}^{+} について,

a ∈ A ⇔ ⟨{0,…, n − 1}, c_{min}, c_{max} ≤, BIT, X^{a}⟩ ⊧ θ

が成り立つことをいう (上の式の右辺を a ⊧ θ で表す). ここで c_{min}, c_{max}, BIT, X^{a} はそれぞれ

c_{min} = 0, c_{max} = n − 1
∀x, i < n(BIT (x, i) ↔ x の 2 進表現の i ビット目は 1 )
∀i < n(X^{a}(i) ↔ a の i ビット目は 1)

で解釈する.

一般に k 変数述語を考えるときは, 1 変数述語記号 X_{1},…, X_{k} をいれた言語 L_{k} 上で定義 5.1 と同様に定義する. また関数についてはそのビットグラフ

{(x_{1},…, x_{k}, i) : f(x_{1},…, x_{k}) の i ビット目が 1}

が F O に入ることとして定義する.

例. 足し算 a + b のビットグラフは F O である. すなわち

P LUS(x) ⇔ a + b の 2 進表現の x ビット目は 1

は L_{2} sentence で表される.

F O は uniform AC^{0} に一致するがここでは AC^{0} の Turing 機械による characterization を使ってこれを証明する.

定義 5.2. Logtime TM M とは長さ n の (ランダムアクセスの) 入力テープ, 長さ O(log n) の作業テープと, 長さ log n の入力アドレステープをもった Tuirng 機械で, 各ステップにおいて M は入力アドレステープに書かれたアドレスに従って入力ビットを読んで動作する.

Alogtime TM は上の Logtime TM を alternate TM としたものとする. また, constant depth Alogtime TM とは, Alogtime TM で各計算 path の alternation の回数が O(1) のものをいう.

Logtime Hierarchy (LH) とは constant depth Alogtime TM で計算可能な関数のクラスとする.

定理 5.1. (Barrington,Immerman,Straubing) F O = LH.

Proof Sketch. LH ⊆ F O をいうには constant depth Alogtime TM の計算が {0,…, O(log n)} を universe とする構造で first order formula で表現すればよい. (作業テープの長さは O(log n) であることからこれは可能である.)

一方, F O ⊆ LH をいうには, φ ≡ ∃x_{1}∀x_{2} ⋯ Q_{k}x_{k}θ(x⃗) (θ は quantifier free) を first order sentence とするときすべての a ∈ {0, 1}^{+} について

T は a を受理する⇔ a ⊧ φ

となる constant depth Alogtime TM T を構成すればよいが, これは x_{1},…, x_{k} が作業用テープに書かれた Logtime TM T′ で

T′ は a を受理する⇔ a ⊧ θ(x⃗)

となるものが取れることから, alternating stage で x_{k},…, x_{1} を 1 つずつとって作業用テープに書いていき, 最後に T′ を simulate すればよい.

次に T C^{0} は FO に majority quantifier と呼ばれる量化子をつけくわえたものとして定義できる. すなわち,

定義 5.3. φ を論理式とするとき, majority quantifier M を次のように定義する.

Mxφ(x) ⇔ #\{i < n : φ(i)\} ≥ ⌈\frac{n}{2}⌉.

L_{k} に majority quantifier M を付け加えた言語で定義可能な関数のクラスを F O+M で表す.

F O が AC^{0} に一致することと T C^{0} の定義から次は容易にわかる.

定理 5.2. F O + M = T C^{0}.

Immerman は更に, transitive closure (TC), least fixed point (LFP) などの operator を定義し, これらを使って NLOGSPACE,P 等のクラスを表現することによって, 以下のことを証明している.

定理 5.3. [6] (1) F O + posT C = NLOGSP ACE.

(2) F O + LF P = P.

定理 5.4. [6] 有効グラフに関する st-connectivity 問題は AC^{0} 還元可能性について NLOGSP ACE 完全である.

References

1. J. L. Balcazár, J Díaz and J Gabarró, Structural Complexity I, Springer-Verlag, 1988.

2. D. A. M. Barrington, N. Immerman and S. Straubing, On uniformity within NC^{1}, J. Comput. Sustem Sci. 41 (1990), 274–306.

3. S. Buss, Circuit Complexity and Computational Complexity, Lecture Notes at University of San Diego, ftp://math.ucsd.edu/pub/sbuss/Math267A.1992/circuit.ps.

4. A. K. Chandra, L. Stockmeyer and U. Vishkin, Constant Depth Reducibility, SIAM J. Comput. 13(2) (1984), 423–439.

5. J. Håstad, Computational Limitations of Small Depth Circuits, MIT Press, 1988.

6. N. Immerman, Languages that capture complexity classes, SIAM J. Comput. 16 (1987), 760– 778.

7. N. Immerman, Descriptive and Computational Complexity, Proceedings of Symposia in Applied Mathematics 38 (1989), 91.

8. R. Smolensky, Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity, 19th Symposium on Theory of Computing (1987), 77–82.

9. I. Wegener, Complexity of Boolean Functions, 1975.

豊田工業高等専門学校一般学科

E-mail address: satoru@math.human.nagoya-u.ac.jp