跳至內容

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.

參考書目

[編輯]

外部連結

[編輯]