わさっきhb

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

関数問題と判定問題〜素因数分解問題を例に

はじめに,「問題」と「個別問題」を,区別しておきます.例えば
(P1) 35を素因数分解しなさい.
は,素因数分解の個別問題です.それに対し
(P2) 正整数nが与えられたときに,その素因数の一つを求めなさい.
は,素因数分解問題となります.一般に「問題」は,無限個の個別問題からなります.問題は集合,個別問題はその要素,と見ることもできます.簡単な区別の方法として,変数を含んでいれば問題,変数がなければ個別問題,というのがあります.
とはいえP1とP2は,ずいぶんと違った表記に見えます.P1を個別問題としたときの問題は,
(P3) 正整数nを素因数分解しなさい.
となるはずです.
これですが,P2が解けると,P3も解くことができます.実際,P2を解くアルゴリズムにより,pが,nの素因数の一つと分かったとしたら,n'=n/pは正整数となります(さらに,n'<nです).そしてn'が1と等しければ,n=pで素因数分解はおしまいですし,そうでなければ,P2のnのところにn'を代入して,「正整数n'が与えられたときに,その素因数の一つを求めよ.」という個別問題に対して,同様に(再帰的に)素因数を求めていけば,nの素因数の並びが得られ,素因数分解できるというわけです.
では,次の問題はどうでしょうか.
(P4) 正整数pは,正整数nの約数であるか,判定しなさい.
これは,ずいぶんと簡単になったように見えます.nをpで割って,あまりが0ならば約数である,すなわち"yes",そうでなければ約数でない,すなわち"no"とすればいいからです.「素因数」から「約数」になった理由については,あとで説明します.
ちなみに,必ずしも簡単になったわけではありません.というのもこの問題は,pとnという,2つの変数を含む問題だからです.
ともあれもう少しだけ,一見難しい問題を,書いておきましょう.
(P5) 正整数nの素因数の一つに,p以下のものがあるか,判定しなさい.
ここでもし,P5を解く(判定できる)アルゴリズムが存在したら,どうなるかを考えることにします.実は,それを使って,P2そしてP3を解くためのアルゴリズムを,構成することができるのです.
P2が解ければP3が解けることは,すでに説明しましたので,ここではP5を解くアルゴリズムを仮定して,P2を解く方法を説明します.アルゴリズムを繰り返し適用していくのですが,正整数nは固定で,pのほうを変えていきます.
ともあれ最初は,P5においてp=2とします.すなわち「nの素因数の一つに,2以下のものがあるか」を判定します.変数nが残っているように見えますが,さきほど「固定」と言いました.適用時点で値が定まっているわけですので,これはP5の個別問題となり,P5を解くアルゴリズムによって"yes"か"no"かを判定できます.
"yes"の場合は,素因数2が得られたので,おしまいですね."no"と判定された場合には,pを2倍し,「nの素因数の一つに,4以下のものがあるか」を判定します.
そうやって,"no"と判定されるたびに,pの値を2倍していきます.ある値,p'としましょう,のときにはじめて,"yes"であると判定されたとします.(そのようなp'は,nが正整数であれば,必ず存在します.)すると,nの素因数は,p'/2より大きく,p'以下であることが分かります.
次は,「nの素因数の一つに,(3/4)p'以下のものがあるか」を判定します.(3/4)p'は,p'/2とp'のちょうど中間です.これが"yes"なら,nの素因数は,p'/2より大きく,(3/4)p'以下であると言えます.もし"no"なら,nの素因数は,(3/4)p'より大きく,p'以下です.
そうやって,素因数の範囲を狭めていき,二分探索法を用いることで,最終的に,nの最小の素因数を求めることができます.ちなみに求めるまでのP5の適用回数は,その最小の素因数がbビットだとすると,2b回となります*1.また「ちょうど中間」については,足したり2で割ったりすることなく,ビット演算で求めることができます.例えばn=35とすると,pの値は2,4,8,6,5と変化しまして,「35の素因数の一つに,4以下のものはないが,5以下のものはある」ことから,その素因数は5となります.
あらためて,P1からP5までを並べ,見直すことにしましょう.

(P1) 35を素因数分解しなさい.
(P2) 正整数nが与えられたときに,その素因数の一つを求めなさい.
(P3) 正整数nを素因数分解しなさい.
(P4) 正整数pは,正整数nの約数であるか,判定しなさい.
(P5) 正整数nの素因数の一つに,p以下のものがあるか,判定しなさい.

このうち,計算論では,P1のみが個別問題,P2からP5までは問題と呼ばれます.P2やP3のように,整数値やビット列など,値を求める問題を「関数問題」といいます.それに対し,P4やP5のように,"yes"か"no"かという1ビットの値を出力することになる問題を「判定問題」と言います.形式的には,問題を,0と1の並びでも何でもいいのですがエンコーディングして(「語」と呼ばれます),"yes"と判定されるべきもののみからなる集合(「言語」と呼ばれます)を正しく特定できるかが,問われることとなります.
あとは,P4とP5の違いですね.P4は「約数」と書いていますが,実は,割り切れるか否かの判定ができますかと問うています.なので,剰余演算を行う操作を利用するか,わり算ほかの演算を使って構成すれば,おしまいです.それを繰り返し使えば,
(P4') 正整数pは,正整数nの素因数であるか,判定しなさい.
を解くこともできます.実際,「pはnの素因数である」とは,「pはnの約数である」と「pは素数である」を同時に満たすことです.また「pは素数である」は,「pは2,3,4,…,p-1のいずれの約数でもない」です(このうちp-1のところは,より小さな上界に置き換えることができます).P4から
(P4'') 正整数qは,pの約数であるか,判定しなさい.
という問題をつくります.この時点でpは定数となりますが,qは変数です.このqを,2から1ずつ上げていき,P4を解くアルゴリズムを繰り返し適用することで,pが素数かどうかを判定できるという次第です.
P4やP4'の形式の判定問題は,「非決定性」の概念と関わりがあります.というのもの,それらを解く(判定する)決定性のアルゴリズムをつくれば,それをもとに,P2,P3,P5を解くこともできます.P5に関して言うと,素因数の一つを非決定性手続きにより生成するフェーズと,その値が確かに素因数になっていることを検証するフェーズに分ければいいのです.「非決定性アルゴリズム多項式時間で解ける問題」は「決定性アルゴリズム多項式時間で解が検証できる問題」と同一視されます.
それに対し,P5のように,「p以下のものがあるか」といった記述を含む判定問題は,NP困難あるいはNP完全な問題で,見かけることがあります.例えばナップサック問題と呼ばれるものは,wikipedia:ナップサック問題によりますと,「…,容量C以内でナップサック内の品物の価値の合計がV以上になるような品物の選び方はあるか」といった形で表されます.

なにこれ

7月8日の授業で説明した「問題と個別問題」「PとNPとNP完全」の拡張版です.

(最終更新:2013-07-19 朝)

*1:あるいは,正整数nがBビットだとすると,2B回以下と言うことができます.