PP (計算複雑性理論)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/30 03:27 UTC 版)
計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は 確率的多項式時間 (probabilistic polynomial time) を意味する。1977年、ジョン・ギルが定義した[1]。
- ^ J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.
- ^ Lance Fortnow. Computational Complexity: Wednesday, September 04, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
- ^ R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991, pp. 1–9, 1991.
[続きの解説]
「PP (計算複雑性理論)」の続きの解説一覧
- 1 PP (計算複雑性理論)とは
- 2 PP (計算複雑性理論)の概要
- 3 参考文献
このページでは「ウィキペディア」からPP (計算複雑性理論)を検索した結果を表示しています。
Weblioに収録されているすべての辞書からPP (計算複雑性理論)を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からPP (計算複雑性理論)を検索
Weblioに収録されているすべての辞書からPP (計算複雑性理論)を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からPP (計算複雑性理論)を検索 - PP (計算複雑性理論)のページへのリンク
