パリティ関数

ブール代数において、パリティ関数（パリティかんすう、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)。

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

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

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$ による値は自動的に一意的に定められる。

無限パリティ関数は、その簡単な定義と、一方でその記述論的複雑さから、理論的な計算科学や集合論でよく使われる。例えば、逆像$f^{-1}[0]$が非ボレル集合であることを示すことができる。

関連項目

• Walsh function
• パリティビット
• Piling-up lemma
• Multiway switching
• 誤り検出訂正

参考文献

• Håstad, Johan (1987), Computational limitations of small depth circuits, Ph.D. thesis, Massachusetts Institute of Technology, http://www.nada.kth.se/~johanh/thesis.pdf.