はじめに，「問題」と「個別問題」を，区別しておきます．例えば
(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以上になるような品物の選び方はあるか」といった形で表されます．
*1:あるいは，正整数nがBビットだとすると，2B回以下と言うことができます．
