ＮＰ困難な問題の理由

質問

ナップサック問題や、巡回セールスマン問題がコンピュータで解くのが難しいといわれているわけをわかりやすく教えてください！

回答No.1

trytobe · ベストアンサー

基本的に総当たり制で答えを探すしかアルゴリズムがないので、データ数が増えると一気に総当たりすべきパターン数が増えてしまい、人間が生きている間に計算が終わらないくらいに膨大になるからです。

このような、データ数に対して多項式時間で解けない問題（NP）が、多項式時間で解けるアルゴリズムが発見されると、寝ている間には解決できるようになって世の中の限界が大きく広がるのです。おそらく、量子コンピュータが実用化されて、複数のパターンを同時並行で計算処理できる性質をつかって総当たりできるようになるほうが早いとは思うのですが。