パリティ機能

ブール代数では、パリティ関数は、入力ベクトルに奇数個の 1 がある場合にのみ値が 1 になるブール関数です。2 つの入力のパリティ関数は、 XOR関数とも呼ばれます。

パリティ関数は、ブール関数の回路の複雑さの理論的調査における役割で注目に値します。

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

-変数パリティ関数は、ベクトル内の 1 の数が奇数の場合にのみ となる特性を持つブール関数です。言い換えると、は次のように定義されます。 ${\displaystyle n}$ ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle f(x)=1}$ ${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle f}$

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

ここで、 は排他的論理和を表します。 ${\displaystyle \oplus}$

パリティは 1 の数のみに依存するため、対称ブール関数になります。

n変数パリティ関数とその否定は、すべての選言正規形が長さnの単項式の最大数 2 ^{n  − 1を}持ち、すべての連言正規形が長さnの節の最大数 2 ^{n  − 1}を持つ唯一のブール関数である。^[1]   

計算複雑性に関する最も初期の研究の1つは、1961年にベラ・スボトフスカヤが、パリティを計算するブール式のサイズが少なくとも でなければならないことを示す の境界を示したことです。この研究では、ランダム制約法が使用されています。 のこの指数は、パターソンとズウィック(1993)によって慎重な分析を通じて まで増加し、その後、ハスタッド(1998)によってまで増加しました。 ^[2]${\displaystyle O(n^{3/2})}$${\displaystyle 3/2}$${\displaystyle 1.63}$${\displaystyle 2}$

1980年代初頭、メリック・ファースト、ジェームズ・サックス、マイケル・シプサー^[3] と、独立にミクローシュ・アジタイ^{[4] は、パリティ関数の定数深度}ブール回路のサイズに関する超多項式下限を確立しました。つまり、多項式サイズの定数深度回路ではパリティ関数を計算できないことを示しました。同様の結果は、パリティ関数からの簡約によって、多数決、乗算、推移閉包関数についても確立されました。^[3]

Håstad (1987) は、パリティ関数の一定深さのブール回路のサイズについて、厳密な指数下限を確立しました。Håstadのスイッチング補題は、これらの下限に使用された重要な技術的ツールであり、Johan Håstad は、1994 年にこの研究でゲーデル賞を受賞しました。正確な結果は、AND、OR、NOT ゲートを持つ深さk の回路では、パリティ関数を計算するためにサイズが必要であるということです。パリティを計算する深さk の回路でサイズが のものがあるため、これは漸近的にほぼ最適です。 ${\displaystyle \exp(\Omega (n^{\frac {1}{k-1}}))}$${\displaystyle \exp(O(n^{\frac {1}{k-1}})t)}$

無限パリティ関数は、すべての無限バイナリ文字列を 0 または 1 にマッピングする関数であり、次の特性を持ちます:および が有限個の座標のみが異なる無限バイナリ文字列である場合、および が偶数個の座標のみが異なる 場合のみ。${\displaystyle f\colon \{0,1\}^{\omega }\to \{0,1\}}$${\displaystyle w}$${\displaystyle v}$${\displaystyle f(w)=f(v)}$${\displaystyle w}$${\displaystyle v}$

選択公理を仮定すると、パリティ関数が存在し、その数はからまでのすべての関数の数と同じであることが証明できます。と が有限個の座標で異なる場合、次のように定義される関係の同値類ごとに 1 つの代表を取れば十分です。 このような代表があれば、それらすべてを にマッピングできます。残りの値は明確に推定されます。 ${\displaystyle 2^{2^{\aleph _{0}}}}$${\displaystyle \{0,1\}^{\オメガ }}$${\displaystyle \{0,1\}}$${\displaystyle \approx}$${\displaystyle w\approx v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle 0}$${\displaystyle f}$

無限パリティ関数の別の構成は、 上の非主ウルトラフィルタ を使用して行うことができます。 上の非主ウルトラフィルタの存在は選択公理に従い、選択公理よりも厳密に弱いです。任意の に対して、集合 を考えます。無限パリティ関数は、がウルトラフィルタの要素である場合に限り、にマッピングすることによって定義されます。 ${\displaystyle U}$${\displaystyle \omega}$${\displaystyle \omega}$${\displaystyle w:\omega \to \{0,1\}}$${\displaystyle A_{w}=\{n\in \omega \mid \{k\leq n\mid w(k)=0\}{\text{ は偶数}}\}}$${\displaystyle f}$${\displaystyle w}$${\displaystyle 0}$${\displaystyle A_{w}}$

無限パリティ関数が存在することを証明するには、少なくともある程度の選択を想定する必要があります。 が無限パリティ関数であり、その逆像をカントール空間のサブセットと見なすと、 は非測定集合であり、ベールの特性を持ちません。選択公理がない場合、カントール空間 のすべてのサブセットが測定可能であり、ベールの特性を持ち、したがって無限パリティ関数が存在しないことは（ ZFに対して）一貫しています。これは、たとえば ソロベイモデルで当てはまります。${\displaystyle f}$${\displaystyle f^{-1}[0]}$ ${\displaystyle \{0,1\}^{\オメガ }}$${\displaystyle f^{-1}[0]}$

• ウォルシュ関数、連続等価関数
• パリティビット、関数の出力
• 積み上げ補題、独立入力に対する統計的性質
• マルチウェイスイッチング、照明を制御するためによく使用される物理的な実装

関連トピック:

• エラー訂正
• エラー検出