階層構造のカウント

複雑性理論において、計数階層は複雑性クラスの階層である。これは多項式階層に類似しているが、NPがPPに置き換えられている。これは1986年にクラウス・ワグナーによって定義された。^{[ 1 ] [ 2 ]}

より正確には、ゼロ番目のレベルは C ₀ P = Pであり、( n +1)番目のレベルは C _{n +1} P = PP ^{C _n P} (つまり、オラクルC _nを持つPP ) である。^{[ 2 ]}したがって、

• C ₀ P = P
• C ₁ P = PP
• C ₂ P = PP ^PP
• C ₃ P = PP ^{PP PP}
• ...

計数階層はPSPACE内に含まれています。^{[ 2 ]}戸田の定理により、多項式階層PH は P ^PP内に完全に含まれており、^{[ 3 ]}したがって C ₂ P = PP ^PP内に含まれています。

• Torán, Jacobo (1991). 「計数量化子によって定義される複雑性クラス」。Journal of the ACM。38 ( 3 ) : 753–774。doi : 10.1145 /116825.116858。MR 1125929。