パリティ関数

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

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

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

定義
-変数パリティ関数が  で  となるブール関数であるのは、ベクトル  に入っている1の数が奇数であるとき、かつその時限りである。
言い換えると,  は以下のように定義される:

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

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

計算複雑性

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

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

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

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

無限バージョン
無限パリティ関数は関数で、無限二進列を0か1に対応させるもので、次の条件を満たすものである:  と  が無限二進列で有限個の座標でしか違いが無いものであるときに、 であることが  と  の違いが偶数個の座標であることと同値である。

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

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

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

参考文献

 

ブール代数
Circuit complexity
関数
数学に関する記事