ウィキペディア

ZPP

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/12/08 07:08 UTC 版)

計算複雑性理論における ZPP とは、以下の属性をもつ確率的チューリング機械で解ける問題の複雑性クラスである。

• YES または NO の常に正しい解を返す。
• 実行時間に制限はないが、任意の入力長について平均で多項式時間かかる。

なお ZPP とは "Zero-error Probabilistic Polynomial time" の略である。

換言すれば、ZPP に属する問題を解くアルゴリズムは完全に無作為なコインを投げるとも言える。常に正しい答えを返すので、ラスベガス法に分類される。入力長 n に関する多項式 p(n) があるとき、答えを得るまでにかかる時間の平均は p(n) 未満だが、最悪の場合はもっと長くなる。

あるいは、ZPP を以下の属性を持つ確率的チューリング機械で解ける問題のクラスと定義することもできる。

• 常に多項式時間である。
• 解として YES、NO、DO NOT KNOW の三種類を返す。
• 解は DO NOT KNOW でない場合は常に正しい。
• 正解が YES である場合、YES を返す確率は最低でも 1/2 である。
• 正解が NO である場合、NO を返す確率は最低でも 1/2 である。

これら2つの定義は等価である。

ZPP の定義には確率的チューリング機械に基づいている。同様の複雑性クラスとして BPP や RP がある。クラス BQP は別のランダム性を持つ機械である量子コンピュータに基づいている。