問題の分類
院試対策として情報学の勉強をしていて体系的なまとめが欲しかったので自作しました。
解決可能か、解決不能か
計算機にとって解決可能な問題とは、アルゴリズム的な解法が与えられるかどうかによります。アルゴリズム的な解法があるとは、停止するプロセスが明確である、つまり決定性を有する実行可能なステップの順序集合により、その問題の解法が与えられることを言います。そのようなアルゴリズムによる解法が存在するような問題のことを「解決可能問題」といい、そうでないものを「解決不能問題」といいます。
計算量が多項式により有界か？
解決可能問題をさらに分類します。
f(n)が多項式である、または多項式により有界であり、ある問題の解法を与えるアルゴリズムの計算量がO(f(n))であるような問題のことを、「多項式問題」といいます。そうでない問題(例えば計算量が冪乗式)のことを「非多項式問題」といいます。
ある問題が多項式問題の集合Pに属するか否かは、大変大きな関心ごとです。なぜなら、もしPに属さない問題をアルゴリズムにより解こうと思ったら、現実的ではない計算量の時間を必要とすることになり、実際的ではないからです。
非決定性をゆるすかどうか...
意思決定をプログラムを実行する主体に委ねているような命令を含むアルゴリズムは、「非決定的である」といいます。現実の問題の中では、決定的なアルゴリズムでは非多項式問題に分類されるのに、非決定性アルゴリズムを用いれば多項式問題に分類されるような問題があります。そのような問題を「非決定的な
多項式問題(NP問題)」といいます。このような問題の集合をNPと呼ぶことにすると、すべてのPはNPであることが言えます。なぜならば決定的アルゴリズムを非決定的なアルゴリズムにすることは本質的に容易だからです。一方で、すべてのNPがPであるかどうかは未だわかっていないようですが、おそらく異なるクラスに分類されると言われているようです(P≠NP予想)。
感想
文字ばかりだし、内容が高度だし、筆者は正式な情報学の講義を受けている人間じゃないしでもはや誰が参考にするのかという問題。おそらくこの問題自体はNP問題だとぼくは予想しています。