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