パリティ関数

ブール代数において、パリティ関数（パリティかんすう、Parity function）とは、入力ベクトルが奇数個の1を持つ場合かつその時に限り値が1となるブール関数である。2つの入力のパリティ関数はXOR関数としても知られている。

パリティ関数は、ブール関数の回路計算量の理論的調査における役割で注目されている。

パリティ関数の出力はパリティビットである。

定義

$n$ -変数パリティ関数が $f:\{0,1\}^{n}\to \{0,1\}$ で $f(x)=1$ となるブール関数であるのは、ベクトル $x\in \{0,1\}^{n}$ に入っている1の数が奇数であるとき、かつその時限りである。言い換えると, $f$ は以下のように定義される:

f(x)=x_{1}\oplus x_{2}\oplus \dots \oplus x_{n}

ここで $\oplus$ は排他的論理和を表す。

性質

パリティは1の数にのみ依存するので、対称ブール関数である。

計算複雑性

計算の複雑さに関する初期の研究の例として、Bella Subbotovskayaによって1961年に示された、パリティを計算するブール式のサイズは少なくとも $O(n^{3/2})$ でなければならないというものがある。これにはrandom restrictionsの手法が用いられた。この指数部の $3/2$ はその後の慎重な解析によって、PatersonとZwickによって $1.63$ に増加され(1993)、さらにHåstadによって $2$ に増加された(1998)。^[1]

1980年代初頭、Merrick Furst、James Saxe、Michael Sipserの3人^[2]、そしてそれと独立にMiklós Ajtai^[3]が、

パリティ関数に対する constant-depth なブール回路のサイズに関する超多項式下界を確立し、すなわち、多項式サイズの constant-depth な回路ではパリティ関数を計算できないことを示した。同様の結果は，パリティ関数からのreductionによって，多数決関数，乗法関数，推移的閉包関数についても確立された^[2]．

Håstad (1987)では、パリティ関数に対するconstant-depth ブール回路のサイズに関する厳しい指数下界が確立されている。Håstad's Switching Lemmaはこれらの下界を得るのに鍵となるテクニカルな補題で、Johan Håstadは1994年にこの研究でゲーデル賞を受賞した。

無限バージョン

無限パリティ関数は関数 $f\colon \{0,1\}^{\omega }\to \{0,1\}$ で、無限二進列を0か1に対応させるもので、次の条件を満たすものである: $w$ と $v$ が無限二進列で有限個の座標でしか違いが無いものであるときに、 $f(w)=f(v)$ であることが $w$ と $v$ の違いが偶数個の座標であることと同値である。

選択公理を仮定すると、パリティ関数の存在とそれが $2^{\mathfrak {c}}$ 個あることが容易に示せる。これは $\{0,1\}^{\omega }$ から $\{0,1\}$ への関数全体の濃度と同じである。これには次の同値関係 $\approx$ の代表系を一つ取ればよい: $w\approx v$ は $w$ と $v$ の違いが有限個の座標に留まることである。このような代表系がとれたとき、代表元は全て0に写すとすれば、残りの関数に対する $f$ による値は自動的に一意的に定められる。

無限パリティ関数の別の構成法として、 $\omega$ 上の非単項超フィルター $U$ を使うものがある。 $\omega$ 上の非単項超フィルターの存在性は選択公理より真に弱い。超フィルター $U$ が取れているとして、全ての関数 $w:\omega \to \{0,1\}$ に対して、 $A_{w}=\{n\in \omega \mid \{k\leq n\mid w(k)=0\}$ のサイズが偶数である $\}$ を考える。このとき、無限パリティ関数 $f$ は $w$ のパリティが $0$ であることと、 $A_{w}$ が超フィルター $U$ の元であることと同値であるように定義することで得られる。

無限パリティ関数は、その簡単な定義と、一方でその記述論的複雑さから、理論的な計算科学や集合論でよく使われる。例えば、逆像 $f^{-1}[0]$ が非ボレル集合であることを示すことができる。 $f^{-1}[0]$ はルベーグ不可測であり、ベールの性質も持たない。選択公理を仮定せず、また無限パリティ関数が一切存在しないという状況もソロヴェイモデル（このモデルでは実数の集合が全てルベーグ可測でありベールの性質を持つ）では成り立つ。

参考文献

^ Jukna, Stasys (Jan 6, 2012). Boolean Function Complexity: Advances and Frontiers. Springer Science & Business Media. pp. 167–173. ISBN 978-3642245084
^ ^a ^b Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Computer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13–27, doi:10.1007/BF01744431
^ Miklós Ajtai, " $\Sigma _{1}^{1}$ -Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1–48.

Håstad, Johan (1987), Computational limitations of small depth circuits, Ph.D. thesis, Massachusetts Institute of Technology.

[jukna-1] Jukna, Stasys (Jan 6, 2012). Boolean Function Complexity: Advances and Frontiers. Springer Science & Business Media. pp. 167–173. ISBN 978-3642245084

[FSS-2] Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Computer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13–27, doi:10.1007/BF01744431

[3] Miklós Ajtai, " $\Sigma _{1}^{1}$ -Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1–48.

[1]

[2]

[3]

定義

性質

計算複雑性

無限バージョン

関連項目

参考文献