新着Pick
39Picks
Pick に失敗しました

人気 Picker
何年か前にニュースがありましたが忘れていました.
https://arxiv.org/abs/2007.01409
巡回セールスマン問題はNP完全と言うクラスに属しています.ある巡回経路が与えられたとき,それがある時間以内に巡回できる経路であることを確認するのは,問題サイズの多項式時間以内に可能です(「NP問題」).しかし,逆にある時間以内に巡回できる経路を見つけろと言われたときに,多項式時間以内に見つけることはできないだろうと言われています(「P問題」ではない).それがこの記事の中にある「真に最適な解を効率的に求めるアルゴリズムは存在しない、と考えている」ということ.このアルゴリズムを見つけるか,あるいは存在しないことを証明することが「P≠NP問題」(クレイ数学研究所から100万ドルの賞金が懸けられているミレニアム問題の一つ)です.「、と考えている」という微妙な言い方がポイントです.本当にそうであることを証明すれば100万ドルがもらえます.
多くの研究者はそのようなアルゴリズムは存在せずに「P≠NP」だろうと考えています.でもそうだとすると,この巡回セールスマン問題のような分かりやすく比較的単純で実用的な問題も,今のコンピュータがどれだけ発達しても(たとえAIが爆発的に賢くなってシンギュラリティが起きても)解けないことを意味します.そこで,これを打開するため,今のコンピュータの計算方法と全く異なる「量子コンピュータ」というものを世界が競って開発しているわけです.
まず、ここに書かれていることを理解することが大事なのですが、それすら難解という素人には厳しい記事です。笑

※個人的な見解であり、所属する会社、組織とは全く関係ありません