非決定論的な多項式時間問題とNP完全問題とは何かを理解するのに苦労しています。私は多項式時間で解ける問題が何であるかを理解しており、ウィキペディアでNP問題について見ました。これについて読んだ後、私はいくつかの問題の例について考えようとしました。私が理解しているように、無向での深さ優先探索はNP完全です。これは、グラフが大きい場合（つまり、間違った決定をした場合は、代わりに他の選択を試みることができる）、各決定を非決定的に行うことができるためです（グラフサイズが小さい場合は多項式。）
数学をあまり使わずに、これらすべてのNP用語を簡単な例で簡単に説明できる人はいますか？
NPとNP完全性については、さまざまな考え方があります。NPの定義から始め、次にNPの難しさ、最後にNPの完全性について説明します。
大まかに言うと、PとNPは問題のクラスです。問題はPにあり、 が yes または no の質問 (決定問題) であり、多項式時間で問題を解決するアルゴリズムがいくつかあります。たとえば、「このグラフのノード u からノード v に移動できますか?」という質問。は深さ優先探索で解けるのでPに属します。( DFS は問題ではなくアルゴリズムであるため、DFS 自体はPに含まれていないことに注意してください)。Pの問題の別の例は、シーケンスがソートされた順序であるかどうかをチェックすることです。
正答が多項式時間で検証できるイエスかノーの質問 (意思決定問題) の場合、その問題はNPにあります。たとえば、古典的なNP問題は、既知の重みの一連の重みが与えられた場合に、正確にある量 k の重みをもつ一連の重みを選択できるかどうかを調べるものです (これはサブセット和問題と呼ばれます)。その特性を持つ重みのセットが存在するかどうかを判断するのは難しいかもしれませんが、私が正しいとわかっている重みのセットをあなたに与えるとしたら、あなたは私が正しいものを与えたかどうかを非常に簡単に確認できます.それらを足し合わせて合計kかどうかを確認するだけで重みのセット。
NPが「非決定論的多項式」と呼ばれる理由は、NPについての別の考え方が、問題の正解を多項式時間で何らかの方法で推測できる魔法のアルゴリズムについて考えることにあるからです。つまり、問題の答えを推測でき、多項式時間で実行されるアルゴリズムを作成できる場合、解決しようとしている問題はNPです。. 重みの例に戻ると、この問題に対する推測アルゴリズムは次のように記述できます。どの重みのセットが正しい重みのセットであるかを線形時間で推測することから始めて、それらをすべて足し合わせて合計 k かどうかを確認します。もしそうなら、答えが「はい」であることを報告してください。それ以外の場合は、「いいえ」と言ってください。このプログラムが常に正しい推測を行うことが保証されている場合、解決策のある問題への入力が与えられると、常に解決策を見つけて「はい」と報告し、解決策がない場合は常に間違って推測して「いいえ」と報告します。
現在のコンピュータ サイエンスにおける最も基本的かつ重要な問題の 1 つは、NPにあることが知られている問題がPにもあるかどうかです。つまり、問題の答えを効率的に (多項式時間で)簡単に検証できる場合、常にその問題を効率的に (多項式時間で)解決できるでしょうか? 多項式時間アルゴリズムを使用して答えを生成し、それが正しいかどうかを確認できるため、 Pの問題はNPの問題でもあることが知られていますが、多項式でNPの任意の問題を解決する方法を見つけた人はいません。時間。
この理由は、NP の一部の問題がNP 完全 として知られているためです。これは、(非公式に) NPの他のすべての問題と少なくとも同じくらい難しいことを意味します。これらの問題を効率的に (多項式時間で) 解くことができれば、NPのすべての問題を多項式時間で解くことができます。NPには非常に重要な多くの問題があり、現在のところ適切で高速なアルゴリズムがないため、これは大きな問題です。これもP = NP問題の魅力というのは、非現実的に解くのが難しいと推定される膨大な種類の問題が、実際には効率的に解けることを示すために必要なのは、1 つのアルゴリズムだけだからです。
より正式には、NP の問題は、多項式時間で他のNP問題のインスタンスをその問題のインスタンスに変換できる場合、NP完全と呼ばれます。上記の重みの問題は、ブール式が満足のいく割り当てを持っているかどうかを判断する問題、整数に関する特定の最適化問題を解く問題 (整数計画法) 、一連の場所を訪問する最速のルートを決定する問題 (巡回セールスマン) などの問題です。 )、または最小数の周波数を使用して都市のセル タワーを割り当てる方法を決定する (グラフの色分け)。数独のようなゲームが解けるかどうかの判断もおよびマインスイーパは、任意のボード サイズに対してNP完全であることが知られています。
(いくつかの問題には後者の性質があります - NPの問題は効率的にその問題に変換できますが、それ自体はNPにはありません。これらの問題はNP 困難と呼ばれます。)
実用的な観点から、NP完全またはNP 困難であることが知られている問題を解決するよう求められた場合、適切な時間内に正確な解決策を見つけることを期待しないでください。場合によっては、任意の精度内で効率的に解を近似することさえできません。解決しようとする別の問題を探すか、すべてではないがほとんどの場合にうまくいくヒューリスティックな解決策に身を委ねるのが最善です。
DFS がNP完全であるという最初の考えについては、問題だけがNPまたはNP完全である可能性があります。アルゴリズムはできません。DFS は、グラフの到達可能性の問題を解決するためのアルゴリズムです。グラフ内の 2 つのノードが与えられた場合、最初のノードから 2 番目のノードへのパスはありますか? その問題はNPにあります。パスがあれば簡単に確認できますが、DFS を使用して多項式時間で解決できることがわかっているため、 (おそらく) NP完全ではありません。
お役に立てれば！
うまくいけば、ウェブ上の他のすべてのリソースを使用して、あなたの例を解析しようとします。
いくつかの問題
私は大学で経験則を教えられました: 解が与えられ、その解が迅速に (つまり、多項式時間で) 検証できる場合、その問題は NP にあります。