PP (複雜度)

维基百科,自由的百科全书
跳转至: 导航搜索

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

相關條目[编辑]


參考資料[编辑]

  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. Springer-Verlag. 1996: 127–135. .
  • Burtschick, Hans-Jörg; Vollmer, Heribert. Lindström Quantifiers and Leaf Language Definability. 1999. Template:ECCC. .

外部連接[编辑]