私が今、興味を持って研究対象にしているのは「問題の難しさ」です。

大学入試だと「○○大学の問題は難しい」とか「××大学の問題は簡単だ」と思う事があるでしょう。しかし、この「難しい」という言葉はとても主観的なもので、ある人にとっては難しいけれど、別の人にとっては簡単、というのはよくある事です。そこで誰もが納得するような、客観的な「問題の難しさ」を決めるために、研究者たちは「その問題を解くために必要な計算ステップ数」という基準を用意しました。簡単に言うと、コンピュータがその問題を解くために必要な「計算時間」を「問題の難しさ」と定義した、ということになります。この基準を使って様々な問題を調べると、上手にプログラム（アルゴリズム）を作る事によって、家庭のパソコンでも割と早く解ける問題や、反対にスーパーコンピュータを使っても宇宙の年齢以上の時間をかけないと解けないような問題など、問題の難しさにはっきりとした区別があることがわかってきました。ある種の簡単な問題は「クラスP」という名前がついている区分に分類され、代表的な難しい問題は「NP困難」という分類に属しています。

---

このような研究で明らかになった例をいくつか挙げてみます。

1. 素数判定問題：ある大きな自然数が、素数かどうかを判定する問題
   この問題は長い間、難しいかどうかがわからない問題でしたが、上に述べたような基準ではクラスPに分類される「簡単な問題」であると、インドの研究者による最近（２００２年）の研究でわかりました。
2. 巡回セールスマン問題：すべての都市をちょうど一度だけ訪問し、出発点に戻ってくる道筋のうちで、最も費用が少なくてすむ道筋を求める問題
   これは最小な費用の道筋を求める事はもちろん、最小な費用に対する定数倍の費用しかかからない道筋を求めることさえも「非常に難しい問題」であり、NP困難に属する問題です。
3. 素因数分解：与えられた自然数に対する素因数を求める問題
   この問題はまだ、難しいか簡単かがわかっていない未解決の問題です。

---

難しい問題に対する研究の方法、アプローチは大きく分けて２種類あります。ひとつは「その問題を効率的に解く手段（アルゴリズム）」を発見することです。最も優れた答を早く計算できないのはわかっていますから、この研究では、ある程度ましな答（近似解）を、早い時間で計算できる手段を開発することになります。

そしてふたつめは、「早い時間で計算可能な、ましな答（近似解）の限界」を理論的に明らかにすることです。この限界がわかっていないことには、最初のアプローチの研究に対するゴールがわからず、ただやみくもに研究をすすめることになってしまいます。この限界がどれだけ本当の解に近いのか？を明らかにすることによって、同じNP困難と分類される難しい問題の中でも、近似という観点から問題の難しさをさらに分類することができます。

---

古典物理学に基づいた構造を持つコンピュータ（スーパーコンピュータも含めて、普通に使われているコンピュータはすべてあてはまります）ではなく、近年研究が盛んになってきた量子コンピュータのアルゴリズムを使うと、(３)の素因数分解は「難しくない問題」に分類されます。つまり異なる動作原理をもつコンピュータを考えると、問題の難しさもそれに応じて異なる可能性もあります。

---

大学に入る前、また大学に入った後でも「問題を解くこと」が勉強や研究の中心になることが多いですが、このような「問題の難しさ」といった「問題そのもの」を対象にした研究も盛んに行われているのです。