パリティP

計算複雑性理論において、計算複雑性クラス⊕ P (「パリティ P」と発音) は、非決定性チューリングマシンによって多項式時間で解決可能な決定問題のクラスであり、受理条件は受理計算パスの数が奇数であることです。⊕ P問題の例としては、「与えられたグラフには奇数の完全マッチングがあるか?」があります。このクラスは 1983 年に Papadimitriou と Zachos によって定義されました。^[1]

⊕ P完全問題の例（多対一還元の下で）は⊕SATである：ブール式が与えられたとき、それを満たす割り当ての数は奇数か？これは、還元が簡潔であるため、クック・レビンの定理に従う。^[2]

⊕ P は計数クラスであり、対応する#P問題に対する答えの最下位ビットを見つけるものと見ることができます。最上位ビットを見つける問題はPPにあります。PP は⊕ Pよりもかなり難しいクラスであると考えられています。たとえば、1998 年に Beigel、Buhrman、および Fortnow によって示されたように、P = ⊕ P ≠ NP = PP = EXPTIME である相対化された宇宙 (オラクル マシンを参照) があります。^[3]

戸田の定理はP ^{PP が}PH を含むことを示していますが、P ^{⊕ P が}NPを含むかどうかは知られていません。しかし、戸田の定理の証明の最初の部分はBPP ^{⊕ P が}PH を含むことを示しています。ランス・フォートナウはこの定理の簡潔な証明を書いています。^[4]

⊕ Pにはグラフ自己同型問題が含まれており、実際この問題は⊕ Pに対して低い。^[5]また、 UPの問題はすべて 0 個か 1 個の受け入れパスを持つため、 UP も自明に含まれる。より一般的には、 ⊕ Pはそれ自体に対して低いため、このようなマシンは ⊕ P の問題を即座に 解くことができることから何の力も得られない。

クラス名の ⊕ 記号は、ブール代数の記号 ⊕ を使用して排他的論理和演算子を参照することへの参照である可能性があります。これは、「受け入れる」を 1、「受け入れない」を 0 と見なすと、マシンの結果が各計算パスの結果の排他的論理和になるため、理にかなっています。

• 複雑性動物園: クラスパリティ P