このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
R. Frivalds "Fast Probabilistic Algorithms". Mathematical Foundation of Computer Science (1979), Lecture Note in Computer Science, volume 74,(1979) pp. 57-69
多項式 p(x), q(x) から積 r(x) を求めるには、各項の係数を計算する必要が あります。 n 次式の二つの多項式があり、積和標準型になっていたとします。 (例) これについて、中央付近の係数は n 回程度の掛け算と n 回程度の足し算が必 要になります。 したがって、 O(n2) 回程度の掛け算が必要になります。
しかし、 p(x)q(x) が r(x) と等しいかどうかを調べるのに、乱数を使うと効 率よく求まります。
このようにすると掛け算の回数を O(n) に下げることができます。 但し、必ずしも正解にはなりません。 ではこのアルゴリズムを分析します。
始めに、入力のp,q,r に対して、 p(x)q(x)=r(x) が成り立っているようなも のを考えます。 すると、上記のアルゴリズムにおいて常に a*b=c が成立します。 したがって、 yes instance に関しては必ず yes を出力することがわかりま す。
一方、 p(x)q(x)≠r(x) の場合を考えます。 この時、常に a*b≠c が成り立てば良いのですが、運悪くたまたま a*b=c になってしまうことがあります。 例えば、 p(x)=x, q(x)=x2+3x-2, r(x)=2x3 の時、p(x)q(x)≠r(x) です が、p(1)q(1)=r(1) となります。 このように、 no instance に関しては yes か no を出力します。 つまり、 no instance の時に誤って yes を出してしまうことがこのアルゴリ ズムの問題点になっています。 しかし、この yes を出す確率を計算することができます。
多項式の性質により、0 と恒等的に等しくない n 次式の多項式は高々 n 個の 解しか持ちません。 したがって、 p(x)q(x)-r(x) が恒等的に 0 でないのであれば、これが 0 に なるような x は高々 n 個しかありません。 そのため、乱数の選び方として、 1 から 2n までをランダムに選ぶと、 no instance に対して、 yes を出力してしまう確率は 1/2 以下に、さらに 1 か ら n2 までをランダムに選ぶと、 yes を出力してしまう確率は 1/n 以下に なります。
もちろん、複数回上記のアルゴリズムを行って答えの精度を上げることもでき ます。 上記のアルゴリズムにおいて、 yes が出力された時は yes instance か no instance かいずれかになり得ますが、no を出力したとすると、この回答に は誤りがありません。 たくさん試行して、一度でも no が出れば、入力は no instance であること が分かります。 いま、 no instance を入れたときに誤りを出す確率を p とするとします。 その時、 k 回試行すると全て誤る確率は pk となるため、誤りの確率を減ら すことができます。
n×n の正方行列 A, B, C において、 A*B=C をチェックするアルゴリズムを 考えなさい。 さらに、誤りの確率を計算しなさい。
R. Freivalds "Probabilistic Two-way Machines". International Symposium on Mathmatical Foundation of Computer Science. Lecture Note in Computer Science, Volume 118, (1981) pp.33-45
オートマトンは入力を一回ずつだけ読んで状態遷移し、入力を読み終えた段階 で答えを出力します。 ここで取り上げている Two-way Machine とは、入力を何度でも読 み込めるもので、読み込みテープヘッドが Turing 機械のように左右に動きま す。 入力の始点と終点にはそれを示すマークが付加されています。 また、これに作業用の読み書き可能なテープを付加したものを Two-way Turing 機械と呼ぶことにします。
このような状況で 0n1n という 0 の長さと 1 の長さ が等しいかどうかを判定する問題を考えます。 これは、 Two-way オートマトンだけではなく ω(log n) SPACE Two-way Turing 機械でも受理することはできません。
0n1n が Two-way オートマトンで受理できないことを 示しなさい。
0n1n が ω(log n) SPACE Two-way Turing 機械で受理できないことを示しなさい。
0n1n が O(log n) SPACE Two-way Turing 機械で受理できることを示しなさい。
さて、 Freivalds はこれに関して以下の定理を証明しました。
任意の ε<0 に対して、 0n1n を確率 1-ε で受理する確率的 Two-way オートマトンが存在する。
つまり、確率的な Two-way オートマトンは、 ω(log n) SPACE Two-way Turing 機械より真に能力が高いことを示したことになります。
まず、 c(ε) と d(ε) を以下を満たす十分大きな自然数とす る。
入力列 x が 0n 1m と仮定します。 最初のステップでは、 かどうかを決定的に判 定します。 もし異なっていれば、 n と m は異なりますので reject します。 一方、合同であれば、 n=m または、 が成り立ちます。
次のステップでは、 0の列と 1 の列で試合をします。 互いの列に対して、それぞれ乱数をその長さ分だけ発生させます。 一方が全て 1 が出て、もう一方が少なくとも 0 が一つ以上出たら前者の勝ち とします。 それ以外は引き分けとします。 一方が全て 1 が出る確率は (1/2)n ですので、滅多に勝負はつきません。
もし、 n=m であったら、両者の勝率は等しくなります。 一方、異なっていた場合、例えば n < m なら、 m > n+c(ε) になります。 ここで、どちらかが d(ε) 回勝つまで勝負をするとします。 そのとき、もう一方が 1 勝もしない確率を求めます。
0 側が全部 1 が出る確率を p, 1 側が q とします。 1 回のラウンドで 0 が勝つ確率は p(1-q), 引き分けになる確率は (1-p)(1-q)+pq=(1-p-q+2pq) です。 この時、 0 側が 1 回勝つ確率は次の通りです。
p=q なら、これは 1/2 になります。 よって、 n=m なら、 d(ε)連勝する確率は (1/2)d(ε) で、 これが 0 側と 1 側のどちらかで達成する確率は 2 (1/2)d(ε) です。 これは d(ε) の定義により ε 未満です。
一方、p=(1/2)n, q<(1/2)n+c(ε) の場合を考えます。 まず、次が言えます。
p≥q の時、
これは、左辺÷右辺が 1 より大きいことを示します。
ここで、分母は正、分子は p>q の時は正なので、 1 以上であることがわ かりました。
ここで、 y =x/ (1+ x) = 1 - 1/x より、 x が小さい方が y は小さくなるこ とと、 p/q > 2c(ε) であることを使うと、 0 側が勝つ確率は 2c(ε)/(1+2c(ε)) 以上であることが分かります。 したがって、 d(ε) 連勝する確率は下記の値より大きくなります。
これは 1-ε より大きいです。
したがって、 n=m の時、一方が連勝する確率は ε より小さく、 また、 n≠m の時は必ず reject するか、 1-ε 以上の確率で連勝 します。 よって、連勝したとき reject するようにすれば、これで 0n1n を誤り確率 ε 以下で受理できることになります。
乱数を使う多項式時間の言語判定のクラスを説明します。
確率的 Turing 機械は、0 または 1 が無限に書かれている乱数テープが接 続され、毎ステップに一ますずつ読むことができようになっています。 さらに、 accept と reject という二つの終了状態を持っています。
確率的多項式時間 Turing 機械は、このような確率的 Turing 機械で、入力の 長さに対して、ある多項式ステップで処理を終了するものです。
言語 L が PP に属するとは、 ある確率的多項式時間チューリング機械 M が存在して、 x が L に属するとき M(x) は 1/2 より大きい確率で accept し、 x が L に属さないときは M(x) が accpet する確率は 1/2 以下のものです。
ある言語 L が BPP に属するとは、 ある確率的多項式時間チューリング機械 M が存在して、 x が L に属するとき M(x) は 2/3 より大きい確率で accept し、 x が L に属さないときは M(x) が accpet する確率は 1/3 以下のものです。
ある言語 L が RP に属するとは、 ある確率的多項式時間チューリング機械 M が存在して、 x が L に属するとき M(x) は 1/2 より大きい確率で accept し、 x が L に属さないときは M(x) は必ず reject するものです。
ある言語 L が ZPP に属するとは、 x が L に属するときは M(x) は accept し、 x が L に属さないときは M(x) は reject する 平均実行時間が多項式に抑えられる確率的チューリング機械 M が存在する。
確率的な計算と非決定的な計算を比較します。 NP の定義では、 accept する計算が存在するかしないかという定義でしたが、 NP の計算における 1bit の guess を 0 か 1 の乱数に置き換えてみると、 accept する確率が 0 より大きいか、0 かということになります。 つまり上記のように NP を定義すると次のようになります。
ある言語 L が NP に属するとは、 ある確率的多項式時間チューリング機械 M が存在して、 x が L に属するとき M(x) が accept する確率は 0 より大きい。 x が L に属さないときは M(x) は必ず reject するものです。
一方、非決定性の計算を計算木で考えると、確率的な計算も非決定性の計算に おいて、 accept する木の葉の量に関係して定義できます。 例えば、 PP は非決定性の計算において、 accept する計算が過半数かどうか を調べることになります。
さて、 Savitch の定理つまり NSPACE(p(n)) subseteq DSPACE(p(n)2) の証明 を思い出すと、 PP の計算において、計算木の accept する葉の数を数えるの も決定性の多項式空間でできます。つまり PP subseteq PSPACE になります。
一方、 NP を計算する確率的 Turing 機械に対して、計算の前に 1/2 の確率 で accept すると、yes インスタンスの入力では 1/2 を越える確率で accept しますが、 no インスタンスでは accept の確率は 1/2 のままです。 つまり、この計算は PP に含まれます。
一方 RP に関しては、yes インスタンスで 1/2 以上の accept があるという ことは、少なくとも accept する計算があることになります。 一方 no インスタンスでは accept する計算がないので、これはそのまま NP に含まれることが分かります。
また RP の計算を二回繰り返し、少なくとも一 回は accept される確率を考えると、 yes インスタンスに関して 3/4 以上で ありますが、 no インスタンスは 0 のままです。 このように繰り返すことで、 BPP の定義も満たすことになっています。
また、 L が RP に含まれ、一方で、 L~ も RP に含まれる状態を考えます。 つまり、 L が RP と co-RP に含まれるという状態です。 この時、入力 x に対して、 RP の計算をするプログラムと、 co-RP の計算を するプログラムを交互に動かし、どちらかが accept を出力するまで繰り返す ことを考えます。 この時、計算が終わらない状況も考えられますが、誤った答えを出すことはなく なります。また、正しい答えを出すまでの繰り返し回数を考えると、 yes インスタンスに対しては RP の計算をするプログラムが accept するまで の回数、 no インスタンスに対しては、 co-RP の計算をするプログラムが accept するまでの回数の平均を考えれば良いので、下記のようになります。
つまり、平均で高々 2 回以内に accept されることが分かります。 それぞれの計算は多項式時間ですから、平均実行時間は多項式時間になります。 したがって、 RP co-RP は ZPP に含まれます。
一方、 ZPP の計算に関して、適当な時刻で計算を打ちきって、 reject する ことを考えます。 すると、 no-instance に対してはエラーがありません。 一方、 yes-instance に対しては必ず多項式時間で計算が終了する代わりに、 エラーが発生する確率が生じます。
これでこの途中で打ちきる計算が RP の計算になることが示せます。
以上をまとめるとつぎのようになります。
但し、これらに関してこれ以上のことは分かっていません。
フェルマーの小定理は素数に対して、0 と素数の倍数以外では必ず下記の式が 成り立つというものです。
それでは p が合成数の場合はどうでしょうか? ここで、もし、 an-1 を n で割った余りが 1 でない x というような値に なるとき、そのような a が半分以上存在することが示せます。
(x≠1)と仮定します。 ここで、 b^(n-1)≡1 mod n となるような b を集めた集合を S とします。 その時、 (ab)^(n-1) ≡ x mod n となりますので、 実は a^(n-1)≡x となる a の集合の要素数と S の要素数は等しくなります。 別の c^(n-1)≡y mod n なども考えることができますが、それも S の要素数と 同じになります。 結局 n と互いに素な数に対して b^(n-1)≡1 mod n となるような b の要素数 は全体の要素数の約数になることが分かります。 したがって、 値の種類が k 種類あれば 1 となる要素数は 1/k となります。
したがって、次のプログラムは素数なら reject, 合成数なら 1/2 以上の確率で accept になるでしょうか？
とこが、合成数の中でもこのフェルマーの小定理が成立してしまう数が存在し ます。 上記の議論は 1 でない数が一つでもあれば確率 1/2 以下になるというもので したが、すべて 1 では成立しません。 これらの数はカーマイケル数と呼ばれてますが、最小で 561 がありますが、 生成方法なども分かっています。
Solovay と Strassen はフェルマーテストを改良して、合成数なら必ず 1/2 以上の確率で accept するテストを作りました。 下記がそうですが、
Miller と Rabin も別の方式ですが、ほぼ同様の性質を持つテストを作りました。
なお、これらのテストは多項式回繰り返しても多項式時間で済みます。 この時の誤りの確率は (1/2)p(n) となるため非常に小さな誤り確率で判定でき ることになります。
java.math.BigInteger#isProbablePrime メソッドは Miller-Rabin テストを 使用しています。
2002 年に Agrawal と Kayal と Saxena は素数判定が乱数を使わずに多項式 時間でできることを発表しました。 彼らのテストは次のようなものです。
但し、 r を見つけるのに (log n)6 程度かかるため、トータルで (log n)12 程度の計算量がかかります。 その後、 (log n)6 まで計算量は改善されましたが、依然として、 実用的な範囲では確率的なチェックより遅い状況です。