パリティ関数のソースを表示

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

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

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

==定義==
<math>n</math>-変数パリティ関数が <math>f:\{0,1\}^n\to\{0,1\}</math> で <math>f(x)=1</math> となる[[ブール関数]]であるのは、ベクトル <math>x\in\{0,1\}^n</math> に入っている1の数が奇数であるとき、かつその時限りである。
言い換えると, <math>f</math> は以下のように定義される:
:<math>f(x)=x_1\oplus x_2 \oplus \dots \oplus x_n</math>
ここで <math>\oplus</math> は [[排他的論理和]]を表す。

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

==計算複雑性==

計算の複雑さに関する初期の研究の例として、[[Bella Subbotovskaya]]によって1961年に示された、パリティを計算する[[ブール式]]のサイズは少なくとも<math>O(n^{3/2})</math>でなければならないというものがある。これにはrandom restrictionsの手法が用いられた。この指数部の<math>3/2</math>はその後の慎重な解析によって、[[Mike Paterson|Paterson]]と[[Uri Zwick|Zwick]]によって<math>1.63</math>に増加され(1993)、さらに[[Johan Håstad|Håstad]]によって<math>2</math>に増加された(1998)。<ref name="jukna">{{cite book|last1=Jukna|first1=Stasys|title=Boolean Function Complexity: Advances and Frontiers|date=Jan 6, 2012|publisher=Springer Science & Business Media|isbn=978-3642245084|pages=167–173}}</ref>

1980年代初頭、[[Merrick L. Furst|Merrick Furst]]、[[James Saxe]]、[[Michael Sipser]]の3人<ref name="FSS">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&#x2013;27, {{doi|10.1007/BF01744431}}</ref>、そしてそれと独立に[[Miklós Ajtai]]<ref>Miklós Ajtai, "<math>\Sigma^1_1</math>-Formulae on Finite Structures", ''[[Annals of Pure and Applied Logic]]'', 24 (1983) 1&#x2013;48.</ref>が、

パリティ関数に対する constant-depth な[[ブール回路]]のサイズに関する超多項式[[順序集合#下界|下界]]を確立し、すなわち、多項式サイズの constant-depth な回路ではパリティ関数を計算できないことを示した。同様の結果は、パリティ関数からのreductionによって、多数決関数・乗法関数・推移的閉包関数についても確立された<ref name=FSS/>。

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

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

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

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

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

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

==参考文献==
{{refbegin}}
{{reflist}}
* {{citation|first=Johan|last=Håstad|authorlink=Johan Håstad|title=Computational limitations of small depth circuits|year=1987|publisher=Ph.D. thesis, Massachusetts Institute of Technology|url=http://www.nada.kth.se/~johanh/thesis.pdf|postscript=.}}
{{refend}}

{{DEFAULTSORT:はりていかんすう}}
[[Category:ブール代数]]
[[Category:Circuit complexity]]
[[Category:関数]]
[[Category:数学に関する記事]]