第43回コラム
「研究の実用性」
情報アーキテクチャ専攻 助教 清水將吾
研究の実用性
自身の研究で、ある問題の計算複雑さを示すというアプローチを取ることがよくある。この種の研究では、対象とする問題がある計算量クラスCで解けることを示すと同時に、C以下では解けないことを示すという困難性の概念が重要である。C困難性が意味することは、どんなに頑張って考えても、Cより効率的に解くアルゴリズムは存在しないことが理論的に証明された、ということである。現代の計算機モデルでは、NP完全と呼ばれる非決定性で多項式ステップの計算を要するクラスから上のクラスに属する問題は現実的な時間で解くことができない。残念ながら、現実の少し複雑な問題（例えば、入力のすべての組合せを考えなければ最良解が得られないような問題）は、現実的な時間では解くことができないことが示されている。例えば、論理変数により構成された論理式が与えられたとき、それを真にするような変数割当てが存在するかどうかを判定する問題は、式のサイズが大きくなれば現実的な時間で解くことができない。また、与えられたアルゴリズムと入力に対してその計算が停止するか否かを判定する問題のように、そもそも計算機で解くことができない問題も存在する（この問題の決定不能性の議論はゲーデルの不完全性定理と同様）。
ところで、この手の研究成果の発表を行うと、私の説明が悪いだけかも知れないが、ほぼ間違いなく実用面での有用性について質問を受けることになる。研究の主要な結果が「ある問題が現実的な時間では解けないことを示した」と否定的に聞こえてしまうからである。もちろん、解けるか解けないか不明であった問題が結局解けないことを明らかにした、このままでは効率良く解けないことが分かったので（それを避ける）多項式時間で解けるような条件を示した、などの主張は可能であるが、「新しいサービスを実現した」とか「従来手法と比較してx%高速化した」のような主張の研究と比較して、実用性を問われると苦しい説明になることは否めない（困難性が直接役に立つ例外的な領域は、効率良く解けることが嬉しくない暗号のような問題である）。更に悪いことは、苦労して証明した結果が、結果的には直観と一致してしまうことが多い（従って、説明は納得されるが驚きもされない）。
しかし、新たに出現した少し難解に思える問題に対する解法を考えるとき、まずは正攻法で最良解を求めることが難しいことを示さないことには話が始まらない。なぜ発見的手法やその他の手法に頼らなければいけないか、または、なぜ効率良く解くために問題を限定しなければならないかといった質問に対して、それなしでは説明ができないからである。困難性が理論的に示されれば、常に最良解を求めようとする労力に終止符を打つことができる。このように、困難性の結果はそれ自身よりもむしろ、現実的な解法の開発に向けた「次の」研究の意義を支える役割を果たす。
上で述べた計算複雑さの研究の例は自身の少ない経験の範囲であり取るに足らないことであるが、大げさに言えば知恵の積上げとしての新規性が求められる個々の研究とその成果の実用性はいつも興味を引く応用でもって一対一に対応しているとは限らない。最近特に短期間での成果を問われることが多く、実際どのような研究でも見通しが必要であることに異論はないが、実用性を意識するあまり大局的な観点での位置付けを見失い、魅力的な枝葉部分ばかりを追うことになってしまっては、理工学的な意味で本質的な何かを生み出す側に回ることはできないと考える。専門職大学院である本学に属する一教員としては、情報科学/IT分野における研究と実用性のよいバランス点を探しながら（これが私には簡単ではないが努力はして）教育研究活動を進めていきたいと考えている。