PP (复杂度)

在计算复杂度理论内，PP是一个复杂度类，包含可以在多项式时间里面以概率图灵机解决，无论输入如何错误率均小于1/2的决定型问题。PP这个缩写即代表了概率多项式时间（probabilistic polynomial time）。这个复杂度类是由Gill于1977年定义^[1]。

相关条目

• PostBQP

参考资料

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..

外部链接

• Complexity Zoo: PP（页面存档备份，存于互联网档案馆）