わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

P=NP問題を理解するためのステップ〜決定性と非決定性の違いが分かる具体例,ある?

情報セキュリティの授業で,「もしP=NPならば,現代暗号の安全性が根底から崩れる」ということを示すため,その前提となる要素を駆け足気味に説明しました.おそらく学生には,計算理論の面白いところが伝わらず,「なんじゃこら」だったのではないかと思います.そこで,この日記で何回かに分けて,疑問に答える形で解説を試みることにします.

決定性と非決定性の違いが分かる具体例,ある?

素因数問題を通して,通常(決定性の)のアルゴリズムと,非決定性操作を用いたアルゴリズムとで,どうなるかを考えていきましょう.具体的には,次の問題を設定します.

2以上の正の整数nが与えられたとき,nを割り切る素数の一つを求めなさい.

議論を簡単にするため「素数の一つ」と書きましたが,全ての素数を求めるのはそれほど難しくありません.というのも,一つ求めることができたとき,例えばその素数をpとすると,n/pも整数となります.そしてこれが1ならば,素因数分解は終了.1でなければ,n/pを入力に与えて,つまり再帰的に素因数分解をすればいいことになります.
さて上の問題を解く概略ですが…求めたい素数の候補を,上位ビットから「出して」いきます*1
最上位のビットは必ず1で,次のビットは「1」か「0」のいずれか.3ビット目以降は,「1」,「0」のほか,「そこで素数生成を終了」という選択肢も考慮に入れます.
もし求めることになる素数がbビットなら,

  1. 最初のビットは選択なし
  2. 2ビット目からbビット目までは,0か1のいずれか
  3. b+1ビット目は出さず,ここで終了

なので,値の候補は,2^{b-1}通りあります.
ここからが重要ですが,決定性のアルゴリズムでは,この値の候補のいずれが解なのかは分からないので,愚鈍ではありますが,それぞれの候補(qという名前をつけましょう)について,qが素数であること,nがqで割り切れることを確認できれば,そのqが答えとなります.最初に出た候補が解かもしれませんが,終わりのほうにならないと,出てこないかもしれません.bビットの中で一つしか条件を満たす素数がないとすると*2,それを見つけるための候補を求める回数の期待値は,2^{b-1}/2です.
次に非決定性のアルゴリズムでは,上の1〜3で都合のいい選択肢をすいすいと選んでいきます.出てきたビット列をrとしましょう.非決定性のアルゴリズムでも,マナーとして,このrが素数であること,nがrで割り切れることを確認します.そしてrが答えとなって,手続きは終了です.
まだ分かりにいですね.具体例を挙げましょう.
n=35という個別問題に適用します.もちろん人間の目では,35=5×7ですが,順に書いて行きます.

  • 決定性のアルゴリズムを適用すると,
    • 1, 0, 終了という手順で,ビット列「10」を生成します.q=2となり,これは素数だけど,35を割り切りません.
    • 1, 1, 終了という手順で,ビット列「11」を生成します.q=3となり,これは素数だけど,35を割り切りません.
    • 1, 0, 0, 終了という手順で,ビット列「100」を生成します.q=4となり,これは素数でありません.
    • 1, 0, 1, 終了という手順で,ビット列「101」を生成します.q=5となり,これは素数だし,35を割り切ります.ということでこれが答え.
  • 非決定性のアルゴリズムを適用すると,
    • 非決定性操作(都合のいい選択肢を選んでいく)により,1, 0, 1, 終了という手順で,ビット列「101」を生成します.r=5となり,これは素数だし,35を割り切ります.ということでこれが答え.

nが大きくなると,決定性のアルゴリズムでは,生成する(そしてたいていの場合,答えにならないことがあとで確認される)ビット列の数が,爆発的にexplosively大きくなります.「爆発的に大きく」をもう少し具体的に言うと,bの指数関数となります.上で書いた2^{b-1}/2は,確かにbの指数関数です.
一方,nが大きくなっても,非決定性のアルゴリズムでは,都合のいい選択肢を選んでいくことで,解の候補(そして答えになることがあとで確認される)は一つしか出しません*3
というように,決定性と非決定性で,入力サイズが大きくなるにれ,計算時間が劇的に違ってくるわけです.

*1:もちろんもっと効率の良い素因数分解アルゴリズムも存在するわけですが,ここでは,決定性と非決定性の違いを見るための手法とお考えください.

*2:ちょうどbビットの素因数が複数あるときの計算は,煩雑なので省略します.ただし,nが2のべき乗であるとかいった極端なものでない限り,本文中の議論に大きく影響を及ぼすものにはなりません.

*3:解の候補を求めるよりも,素数であること,nを割り切ることを検証する時間のほうが大きくなります.