Hamilton for Android APK

説明

P 対 NP 問題は、コンピューター サイエンスにおける主要な未解決の問題です。解決策がコンピューターによって迅速に検証できるすべての問題が、コンピューターによっても迅速に解決できるかどうかについて説明します。これは、Clay Mathematics Institute によって選ばれた 7 つのミレニアム賞問題の 1 つで、最初の正解に対して 1,000,000 米ドルの賞金が与えられます。ハミルトニアン サイクル問題は、グラフ理論の分野でよく知られている NP 完全問題です。このような問題を解決することは、たとえば、任意の入力でそれを解決する多項式アルゴリズムを見つけることで、P 対 NP 問題の解決にこれまで以上に人類を近づけることになります。

このゲームでは、ノードとエッジのセットであるグラフが与えられます。グラフにはハミルトニアン サイクルが含まれる場合があり (詳細はこちら https://en.wikipedia.org/wiki/Hamiltonian_path_problem)、含まれない場合もあります。ハミルトン閉路を公開するか、そのグラフには存在しないと判断することによって、それを解決する必要があります。

グラフがハミルトニアン (ハミルトン サイクルを含む) であるかどうかを判断するための大きなヒントは、https://en.wikipedia.org/wiki/Graph_toughness にあります。

さあ、100 万ドルの問題を解決し、その過程でグラフ理論を学びましょう!