Non-uniform Hierarchy Theorem - 某理論計算機科学者の研究日誌

計算量理論の基本的事項の復習です．（証明などはたぶん標準的な計算量理論の教科書に載っていると思います．今回は Arora & Barak の新しい教科書の証明方針を参考にしましたが，微妙に細部が異なっているかと思います．間違っていたらご指摘下さい！）

長い時間動作できるTuring機械は短い時間しか動作できないTuring機械よりも真に計算能力が上である，という所謂「階層定理」はお馴染みの対角線論法で証明されます．

それでは非一様計算モデルの代表格である論理回路ではどうでしょうか？実際，非一様版の階層定理は，大きい回路は小さい回路よりも真に計算能力が上であることを示しています．この定理の証明技法として対角線論法は使えず，代わりに計数法（counting argument）を用います．

定理（non-uniform hierarchy theorem）: 関数 $s, s':\mathbb{N}\rightarrow\mathbb{N}$ は $2^n/100n > s'(n) > s(n) > n$ かつ $s(n)\log{s(n)} = o(s'(n))$ を満たすとすると， $\text{SIZE}(s(n))\subset \text{SIZE}(s'(n))$ が成立する．
証明: $\text{SIZE}(s(n))\subseteq \text{SIZE}(s'(n))$ であることは自明なので， $\text{SIZE}(s(n))\neq \text{SIZE}(s'(n))$ であることを示す．そのためにまず以下の二つの補題を示す．

補題1: 十分大きな全ての $n\in\mathbb{N}$ に対して，サイズ $2^n/10n$ 以下の $n$ 入力論理回路で計算できない $n$ 入力ブール関数が存在する．
証明: まず $n$ 入力ブール関数の総数は $2^n$ 通りの入力に対する出力値の取り方だけあるので $2^{2^n}$ 個である．一方で $s$ 個の素子のAND,OR,NOTへの割り当て方で $3^s$ 通り，各素子における2つの入力の繋ぎ方が素子ごとに $(s-1)^2$ 通りなので，サイズ $s$ の論理回路の数はせいぜい $3^s\cdot (s-1)^{2s}$ 通りである． $s=2^n/10n$ とすると，十分大きな任意の $n$ で $2^{2^n} > 3^s\cdot (s-1)^{2s}$ となるので，サイズ $2^n/10n$ の論理回路では計算できない $n$ 入力ブール関数が存在する．■

補題2: 任意の $n\in\mathbb{N}$ に対して，任意の $n$ 入力ブール関数はサイズ $2^{n-1}\cdot 5-4=O(2^n)$ の $n$ 入力論理回路で計算可能である．
証明: 与えられた任意の $n$ 変数ブール関数 $f(x_1,x_2,...,x_n)$ に対して， $f(x_1,x_2,...,x_n)= (x_1\wedge f(1,x_2,...,x_n)) \vee (\overline{x_1}\wedge f(0,x_2,...,x_n))$ が成立することは $x_1$ に値0と1を代入すればすぐに確認できる．よって， $k$ 変数ブール関数を計算するのに十分な素子数を $g(k)$ とすると，上の関係式より， $n$ 変数ブール関数の計算には，2回の $n-1$ 変数ブール関数の計算には $2g(n-1)$ 個の素子，NOT素子1個，AND素子2個，OR素子1個で十分であることが分かる．したがって $g(n)\le 2g(n-1)+4$ である．また明らかに $g(1)=1$ である．この漸化式を解くと， $g(n)\le 2^{n-1}\cdot 5-4$ が得られる．■

これらの補題を使って定理の証明を行う．まず補題1より，十分大きな全ての $m$ に対してサイズ $2^m/10m$ の回路で計算できない $m$ 入力ブール関数 $f$ が存在する．補題2より，この関数はサイズ $(5/2)\cdot 2^m$ の回路で計算可能である．
$m=\lceil\log(\frac{2}{5}s'(n)) \rceil$ とおき， $n$ 変数ブール関数 $f'$ を最初の $m$ ビット入力に対して $f$ を計算してその結果を出力とする（残りの入力に対しては何もしない）関数として定義する．このとき，[tex:f'\in\text{SIZE}*1]である．また $f'\notin\text{SIZE}(2^m/10m)$ であるが， $s(n)\log{s(n)} = o(s'(n))$ であるため， $\text{SIZE}(s(n))\subseteq\text{SIZE}(2^m/10m)$ である．したがって $f'\notin\text{SIZE}(s(n))$ である． $f'\in\text{SIZE}(s'(n))$ かつ $f'\notin\text{SIZE}(s(n))$ なので $\text{SIZE}(s'(n))\ne\text{SIZE}(s(n))$ が言える．■

*1:5/2)2^m)\subseteq \text{SIZE}(s'(n