米ノートルダム大学は2018年12月11日(米国時間)、同大学物理学部教授で、コンピュータ科学工学部併任教授のゾルタン・トロツカイ氏らの研究チームが、デジタルの枠組みを超えてコンピュテーションを進化させる新しい数学的アプローチの開発に取り組んでいることを明らかにした。 2018年11月に「Nature Communications」で発表された同チームの最新の論文は、「NP困難問題」の最適解を発見できる可能性がある新しい数学的なアナログ“解法”を解説している。論文では充足最大化問題(MaxSAT問題)を扱った。 NP困難とは、計算量理論で定義されている用語で、ある問題を解くためにどの程度の計算能力が必要なのかを指す用語。NP困難な問題では、必要な計算量が問題の規模に比例せず、指数関数的に増えてしまう。例えば問題の規模が100倍に拡大すると、必要な計算時間が100倍ではなく、2の100乗倍に
![アナログコンピュータ用の数学的解法を開発、ノートルダム大](https://cdn-ak-scissors.b.st-hatena.com/image/square/8d188265421832c6bce7323d007e6fa442b64f63/height=288;version=1;width=512/https%3A%2F%2Fimage.itmedia.co.jp%2Fait%2Farticles%2F1812%2F25%2Fcover_news004.jpg)