パスワードを回復しようとしました。このことを考えたとき、「パスワードの回復」という問題が NP 問題の非常に良い例であることに気付きました。パスワードがわかっている場合は、多項式時間で簡単に確認できます。しかし、パスワードがわからない場合は、指数関数的な時間がかかることが示される可能性のあるソリューションの全領域を検索する必要があります。
ここで私の質問は次のとおりです。「パスワードの回復」は、実行に多項式時間以上を必要とすることが示される NP の要素であるため、これは P != NP であることを示していませんか?
「パスワード回復」を解決するアルゴリズムが多項式時間を超える必要があることを示す場合、それはP≠NPであることを示しています。
それ以外の場合、1つの特定の解が多項式時間を超える必要があることを示すだけでは、何も示されません。指数関数的な時間を必要とするソートを作成できます（ソートされるまで配列をシャッフルします）が、それは多項式の解がないという意味ではありません。
NPは、それがあなたが考えていたものである場合、「非多項式」を意味するものではありません（そして、そうでなかった場合は、事前に謝罪します！）。これは「非決定論的多項式」を意味します。非決定性アルゴリズムは、アルゴリズムの無制限の数の並列インスタンスに相当するものです。例として、ブルートフォースによって正しいパスワードを見つけることは非決定論的な多項式です：パスワードをチェックすることを想像した場合、推測が正しい場合は、パスワードの長さに線形（つまり多項式）の時間がかかりますが、任意の数の可能なパスワード（k ^ n）を並行してチェックすると、この方法を使用して解を見つけるコストは非決定論的な多項式になります。
非決定論的アルゴリズムは、状態がいくつかのステップで分岐するアルゴリズムと考えることもできます。この簡単な例は、非決定性有限オートマトン（NFA）です。状態間でどのエッジを取るべきかわからない場合があるため、両方を使用します。すべてのNFAが決定性FAと同等であることを示すのは簡単です。したがって、他の興味深いクラスのアルゴリズムでも同じことが証明できると考えるのは魅力的です。残念ながら、多項式アルゴリズムの一般的なケースではそうすることは困難であり、一般的な疑いは、それらが同等ではない、つまりP！=NPであるということです。
問題が NP にあるという推論は正しいです。多項式時間で検証できる場合、それは NP にあります。非常に単純な問題でさえ NP にあります。基本的に、P はすべて NP に含まれます。(*)
さて、これを P != NP の証明に変える 1 つの方法を次に示します。
1) 「パスワード回復」が NP 完全であることを示す。つまり、NP の問題は、多項式時間で「パスワード回復」に還元できます。(つまり、他の NP 問題を「パスワード回復」に変換する効率的なアルゴリズムがあります。)
2) それができたら、Pavel Shved が言及しているように、直感的なアルゴリズムが非多項式であることを示すだけでは不十分です。「パスワード回復」を解決するための多項式アルゴリズムが存在しないことを示す必要があります。非常に難しい作業です。
(*) Edmund も正しい: NP は非決定論的マシン上の多項式を意味します。多項式検証は、本質的に非決定論的マシンによって選択されたパスです。
n!一連のn個別の整数の順列がありますが、昇順で並べ替えられているのは 1 つだけですが、n log n時間内に見つけることができます。より楽しい例については、Project Euler #67を参照してください。P・NP等の詳細はこちら この前の質問を参照してください。
この問題の正式なステートメントは、入力としてハッシュ値 (およびソルト) を受け入れ、そのハッシュを生成するパスワードを見つけようとするものです: 基本的な既知の暗号文の衝突検出の問題です。
ハッシュの品質によっては、指数関数的な時間が必要ない場合があります。実際、広く使用されている暗号化ハッシュの多くは、キースペース検索よりも高速に実行される攻撃を特定しています。
つまり、あなた (および他の応答者の一部) は、パスワード変更ルーチンには、設計者が必要とするすべてのプロパティがあると想定しています。これは証明されなければなりません。
問題は、パスワードの回復が非多項式であることを示しているわけではありません。明らかに多項式であるためです。回答の指数空間を検索する必要があります。
実際、「パスワード回復」は、実際には標準的な計算問題の説明ではありません。正式には、パスワード解読アルゴリズムは、特定の文字列が正しいパスワードであるかどうかを答えることができるある種の「オラクル」を使用しているようです。ただし、P と NP は、文字列を入力として受け取るチューリング マシンの観点から定義されています。