ZPP
計算複雑性理論における ZPP とは、以下の属性をもつ確率的チューリング機械で解ける問題の複雑性クラスである。
なお ZPP とは "Zero-error Probabilistic Polynomial time" の略である。
換言すれば、ZPP に属する問題を解くアルゴリズムは完全に無作為なコインを投げるとも言える。常に正しい答えを返すので、ラスベガス法に分類される。入力長 "n" に関する多項式 "p"("n") があるとき、答えを得るまでにかかる時間の平均は "p"("n") 未満だが、最悪の場合はもっと長くなる。
あるいは、ZPP を以下の属性を持つ確率的チューリング機械で解ける問題のクラスと定義することもできる。
これら2つの定義は等価である。
ZPP の定義には確率的チューリング機械に基づいている。同様の複雑性クラスとして BPP や RP がある。クラス BQP は別のランダム性を持つ機械である量子コンピュータに基づいている。