PP (複雜度)

在計算複雜度理論內，PP是一個複雜度類，包含可以在多項式時間裏面以概率圖靈機解決，無論輸入如何錯誤率均小於1/2的決定型問題。PP這個縮寫即代表了概率多項式時間（probabilistic polynomial time）。這個複雜度類是由Gill於1977年定義^[1]。

參考資料[編輯]

^ J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.

Papadimitriou, C. chapter 11. Computational Complexity. Addison-Wesley. 1994. .
Allender, E. A note on uniform circuit lower bounds for the counting hierarchy. Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science 1090. Springer-Verlag. 1996: 127–135. .
Burtschick, Hans-Jörg; Vollmer, Heribert. Lindström Quantifiers and Leaf Language Definability. 1998. doi:10.1142/S0129054198000180. ECCC（英語：Electronic Colloquium on Computational Complexity） TR96-005. .