答えを言われれば 「あっ，そうか」 と思うけれども， それを見つけるとなると一苦労という問題が， 我々の周囲には意外と多くある． もう少し固くいえば， 「解が与えられれば， それが問題の制約を満たしているのは容易に確かめられるが， その解を見つけ出すのが困難」 な問題のこと． かなり大ざっぱだが， ＮＰ問題とは， こうした特徴を持つ問題の総称である． 私の研究テーマは “問題の難しさの解析”だが， その中でもとくにＮＰ問題の難しさに興味がある．
ＮＰ問題の代表例として箱詰め問題がある． これは， 与えられた箱と長方形の板に対し， 板をすべて箱の中にしまう詰め方を見つけ出す問題だ． 確かに， 詰め方を示されれば， それが問題の条件を満しているかが直ちにわかる． ところが詰め方を見つけ出すのは難しい． 「全部試してみればすむことではないか」 と思われるかもしれない． 板の枚数が少ない場合にはそれでもよいが， 枚数が増えると詰め方が非常に多くなり， 全部を試していたら大変なことになる． たとえば板が 100 枚の場合， スーパーコンピュータを使ったとしても， すべての可能性を調べるのに少なくとも 3500 万年！？かかってしまう． 「全部調べようとするからいけないんだ． もっとよい方法（アルゴリズム）を使えばよい」 という意見もあろう． 確かに工夫次第で 1000 枚ぐらいまでは何とかなるのだが， こうした工夫は本質的な解決ではないので， 板の枚数が 5000 枚くらいになると やはり手に負えなくなってしまう． 実は 「箱詰め問題を含め， ある種のＮＰ問題のあるものに対しては， それをまともな時間内で解くアルゴリズムは存在しない」 と予想されている． これがＰ ≠ ＮＰ予想である． この予想は コンピュータの出現当時からあるのだが， まだその証明の糸口すら見つかっていない． 歴史こそ浅いがその奥は深く， 現代数学における重要な未解決問題の一つといってよいだろう．
先ほど述べたように， 我々の周囲にはＮＰ問題が多い． 資源を効率良く分配する問題， 与えれた仕様を満す機械を自動設計する問題， 等々． コンピュータを利用しようとすると， 必ずどこかでＮＰ問題（を如何に解くか）が鍵となってくるはずだ． そのとき， そのＮＰ問題がどの程度難しいのかが重要になってくる． 実は“難しさ”の尺度は一つではなく， 様々なものが提案されている． たとえば， 仮によい解法がない（単純な意味で難しい）としても， 近似解法ならばあるかもしれない． あるいは大部分の問題例に対してうまく行く方法があるかもしれない． 前者については， たとえば 「箱詰め問題に対してよい解法がなかったとすると， （ある種の）近似解法も存在しない」 ことが証明できた． いまはさらに 「ほとんどのすべての問題例に対してうまく解く方法もない」 ことを示そうと努力している．
結局“難しさ”の解析とは 不可能性を証明することである． 「できないことを示して何がいいの？」 と思われる方も多いだろう． 暗号のように不可能性の証明が応用上重要になってくる場合もあるが， ここでは別の理由を二点挙げてみたい． 一つは， よいアルゴリズムの開発に役立つという点． どこまでが不可能ということがはっきり分ってくると， 何を目標にしてアルゴリズムを開発すればよいかがはっきりし， 考えやすくなる． もう一つは， 情報の価値を正しく評価できるようになるという点． 一般に情報の価値を定めるのは難しい． しかし， その情報（解）を求めることの難しさが客観的に示せれば， 情報の絶対的価値が議論可能になるのでは， と期待している．
では 「何故やっているの？」 と聞かれたら 「おもしろいから」 というのが正直なところだろう． “不可能性”というのは非常にとらえどころがない． それが研究していくうちに見えるようになり， 触れられるようになってきて， そして最後に捕まえられる． この醍醐味は一度やったらやめられないのである．
ところで 工学部に在籍しながら こうした超基礎研究をやっているのは変わった存在かもしれない． 実際， 面と向かって 「あなたは変わっている」 と言われたこともある． （そう言った人も結構変わっている？） しかし， こうした変人でもメンバーの一員として認め， それだけでなく 機会があれば一緒に研究しようという雰囲気が電気情報系学科にはある． これは本学全体にいえる東工大の校風ではないだろうか． この校風を誇りに感じ 大切にして行きたいと思っている．