言語を変えてください

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

マシゴンにサインインする

または

新しいアカウント     パスワードを再設定する     

Untitled CourseAnts

巡回セールスマン問題はNP困難

_計算の複雑さの理論_とは、「難しい」問題をコンピュータでどのように解決するかを決定することです。 NPハード（非決定論的多項式時間ハード）は、最も難しい問題のクラスです。

です。つまり、コンピューターで解決することは非常に困難です（少なくとも多数の都市では）。

高速で正確なアルゴリズムを見つけることは、コンピュータサイエンスの分野で深刻な意味を持ちます。つまり、 すべての NP困難な問題に対して高速なアルゴリズムがあるということです。また、特定の問題がコンピュータにとって非常に困難であると考えられているという事実に依存しているため、インターネットセキュリティのほとんどが役に立たなくなります。

巡回セールスマン問題を解決する高速アルゴリズムを見つけると、数学とコンピューターサイエンスで最も有名な未解決問題の1つである__P対NP__問題も解決されます。これは、7つのミレニアム賞問題の

7つの__ミレニアム賞問題__は、数学で最も難しい未解決問題の一部です。それらは2000年に_Clay Mathematics Institute_によってリストされ、それぞれ100万ドルの報酬を持っています：

  • P対NP

*ホッジ予想

*ポアンカレ予想

*リーマン仮説

*ヤンミルズの存在とマスギャップ

  • Navier-Stokesの存在と滑らかさ

*バーチアンドスウィンナートンダイアー予想

これまでのところ、問題の1つである_ポアンカレ予想_のみが解決されました。しかし、それを解決した数学者、グリゴリペレルマンは賞を拒否しました。

1つであり、それぞれが100万ドルの賞金を獲得しています。

フルコース