ニュース
» 2018年12月25日 15時00分 公開

デジタルの限界に挑む:アナログコンピュータ用の数学的解法を開発、ノートルダム大

米ノートルダム大学などの研究チームが、デジタルコンピュータでは手に負えないNP困難問題について、最適解を発見する可能性があるアナログコンピュータ向けの解法を開発した。

[@IT]

この記事は会員限定です。会員登録(無料)すると全てご覧いただけます。

 米ノートルダム大学は2018年12月11日(米国時間)、同大学物理学部教授で、コンピュータ科学工学部併任教授のゾルタン・トロツカイ氏らの研究チームが、デジタルの枠組みを超えてコンピュテーションを進化させる新しい数学的アプローチの開発に取り組んでいることを明らかにした。

ゾルタン・トロツカイ氏(出典:ノートルダム大

 2018年11月に「Nature Communications」で発表された同チームの最新の論文は、「NP困難問題」の最適解を発見できる可能性がある新しい数学的なアナログ“解法”を解説している。論文では充足最大化問題(MaxSAT問題)を扱った。

 NP困難とは、計算量理論で定義されている用語で、ある問題を解くためにどの程度の計算能力が必要なのかを指す用語。NP困難な問題では、必要な計算量が問題の規模に比例せず、指数関数的に増えてしまう。例えば問題の規模が100倍に拡大すると、必要な計算時間が100倍ではなく、2の100乗倍に増えてしまう。

 このような問題は世の中にありふれている。情報科学の教科書にある「巡回セールスマン問題」や「ナップサック問題」に限らず、例えばある種のスケジューリングやタンパク質の折りたたみ、バイオインフォマティクス、医療画像処理、ASIC(Application Specific Integrated Circuit)の回路設計などに関連するさまざまな問題がNP困難であり、実用的な規模の問題を解こうとしても既知の方法では、最適解を求めるまでに時間がかかりすぎてしまう。

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。