NP の複雑さの理解: 定義と例
NP は「非決定的多項式時間」の略です。これは、問題を解決するのに必要な時間を表す複雑さのクラスです。 NP では、アルゴリズムの実行時間は入力サイズの多項式になる可能性がありますが、非決定論的になることもあります。つまり、アルゴリズムによって選択された特定のソリューションに応じて実行時間が変化する可能性があります。つまり、NP は非決定性マシン上で多項式時間で解決できる問題のクラス。非決定性マシンとは、問題に対して考えられるすべての解決策を並行して試行し、最初にうまくいった解決策を受け入れることができるマシンです。これにより、マシンは、一度に 1 つの解決策しか試行できない決定論的マシンよりもはるかに速くいくつかの問題を解決できます。
NP の問題の例としては、次のものが挙げられます。
* 巡回セールスマン問題 (都市とそのペアの距離のリストが与えられた場合、各都市を 1 回だけ訪問する可能な最短ルートを見つける)
* ナップザック問題 (アイテムのセットとその重量と値が与えられた場合、合計値を最大化する限られた容量のナップザックに含めるアイテムのサブセットを決定する)
*ブール充足可能性問題 (一連のブール変数とその制約が与えられた場合、すべての制約を満たす変数への値の割り当てが存在するかどうかを判断します) NP 複雑度クラスは、多項式で解くのが難しい多くの問題が含まれているため重要です。ただし、決定論的なマシンによって迅速に検証できます。これは、アルゴリズムが多項式時間内に解を見つけることができない場合でも、提案された解を迅速に検証できれば依然として有用であることを意味します。
高く評価
低く評価
コンテンツエラーを報告する
シェア
