このp！= np証明には何が欠けていますか？

Question

パスワードを回復しようとしました。これを考えると、「パスワード回復」という問題がNPの問題の非常に良い例であることを認識しました。パスワードを知っていれば、多項式時間でそれを確認するのは非常に簡単です。ただし、パスワードがわからない場合は、指数関数的な時間をとることが示される可能性のあるソリューションのスペース全体を検索する必要があります。

さて、私の質問は次のとおりです。これは、「パスワードリカバリ」がNPの要素であるため、P！= npは、実行に多項式時間以上を必要とすることが示されることができることを示していませんか？

Answer 1

問題は、パスワードの回復が非政治的であることを示していません。明らかにそうであるため、回答の指数関数的な空間を検索する必要があります。

実際、「パスワード回復」は実際には標準の説明ではありません 計算上の問題. 。正式には、パスワードを破るアルゴリズムは、特定の文字列が正しいパスワードであるかどうかに答えることができるある種の「Oracle」をとるようです。ただし、PとNPはチューリングマシンの観点から定義されており、文字列を入力として使用します。

Answer 2

あなたがそれを示すなら どれか 「パスワードの回復」を解決するアルゴリズムには、多項式時間を超える必要があり、その後、P≠NPであることが示されます。

それ以外の場合は、それだけを示す場合 1つの特定のソリューション 多項式時間以上のものが必要であり、何も示しません。指数時間（ソートされるまでシャッフルアレイ）を要求するためにある種を書くことができますが、それは多項式解決策がないという意味ではありません。

Answer 3

NPは「非皮質」を意味するものではありません。それがあなたが考えていた場合（そして、あなたがそうでない場合は事前に私の謝罪！）。それは「非決定的多項式」を意味します。非決定論的アルゴリズムは、アルゴリズムの並列インスタンスの数のない数に相当するものです。例として、ブルートフォースによる正しいパスワードを見つけることは非決定的多項式です。パスワードをチェックすることを想像する場合、推測が正しい場合は、パスワードの長さで線形（つまり多項式）時間を取る必要がありますが、任意の数の可能なパスワード（k^n）を並行して確認すると、この方法を使用してソリューションを見つけるコストは非決定論的多項式です。

非決定的アルゴリズムは、いくつかのステップで状態が分岐するものについても考えることができます。これの簡単な例は、非決定的有限オートマトン（NFA）です。時には、状態間でどのエッジをとるべきかわからないので、両方を取得します。すべてのNFAが決定論的なFAと同等であることを示すのは簡単であるため、他の興味深いクラスのアルゴリズムでも同じことが証明できると考えるのは興味をそそることです。残念ながら、多項式アルゴリズムの一般的なケースではそうすることは困難であり、一般的な疑いは、それらが同等ではないということです。つまり、p！= np。

Answer 4

問題がNPにあるという理由は正しいです。多項式時間に検証できる場合、それはNPにあります。非常に単純な問題でさえNPにあります。基本的に、すべてのPはNPに含まれています。 （*）

さて、これをP！= np：

1）「パスワードの回復」がNP不完全であることを示します。つまり、NPの問題は、多項式時間の「パスワード回復」に減らすことができます。 （つまり、他のNPの問題を「パスワード回復」に変換する効率的なアルゴリズムがあります。）

2）それを手に入れると、Pavel Shvedが言及しているように、直感的なアルゴリズムが非腸類的であることを示すだけでは十分ではありません。 「パスワード回復」を解決するために、多項式アルゴリズムが存在しないことを示す必要があります。非常に難しい作業。

（*）Edmundも正しい：NPは非決定論的機械で多項式を意味します。多項式検証は、本質的に非決定的機械によって選択されるパスです。

Answer 5

1. 述べたように、「パスワードの回復」は決定の問題ではありません。
2. 「パスワードの回復」には多項式時間アルゴリズムがないことを証明していません。単に、そうではないという直感的な根拠について議論しました。ソリューションスペースが巨大であるからといって、ソリューションを見つけるための高速なアルゴリズムがないという意味ではありません。たとえば、あります n! 一連の順列 n 明確な整数ですが、1つだけが昇順でソートされていますが、で見つけることができます n log n 時間。もっと楽しい例については、参照してください プロジェクトオイラー＃67.
3. 「パスワード回復」を決定問題として言い換え、それを解決するための多項式時間アルゴリズムがないことを示すことができたとしても、「パスワードの回復」がNP不完全であることを証明する必要があります。

p/np/etcの詳細については。これを参照してください 前の質問.

Answer 6

この問題の正式な声明は、ハッシュ値（および塩）を入力として受け入れ、見つけようとするものになります。 a そのハッシュを生成するパスワード：あなたの基本的な既知のcyphertext衝突発見の問題。

ハッシュの品質に応じて、これ ではないかもしれない 指数時間が必要です。実際、多くの暗号化が広範囲に使用されているため、多くの暗号化されたハッシュされているため、キースペース検索よりも速く実行される攻撃が特定されています。

つまり、あなた（他の応答者の一部）が持っています 想定されています パスワードマンギングルーチンには、設計者が望んでいたすべてのプロパティがあること。これはそうでなければなりません 証明されました.

Answer 7

この答えを書くと、ある時点でこのアイデアがあり、ここでの答えは満足のいくものではありませんでした。

あなたは、「オラクル」の存在下でp =/= npであることを証明しました（これは、パスワードが正しいかどうかを示すものです）。

オラクルを使用して、元のP vs NPを実際に証明できないことが示されています（この手法は相対化と呼ばれます）。

元の問題を証明するには、チューリングマシンの観点からオラクルを定義する必要があります。言い換えれば、パスワード検証者が入力で何をするかを説明し、パスワードの検証剤コードを考慮してパスワードを推測できるアルゴリズムがないことを証明する必要があります。

可能な高速パスワード検証者に対してこれを行う必要があることに注意してください。パスワードVerifierアルゴリズムの唯一の要件は、パスワードの長さに関してポリノーム時間で実行されることです。

したがって、パスワードが正しいかどうかをチェックする可能性のあるアルゴリズムがポリノーム時間であるかどうかを考えると、検証剤アルゴリズムを読み取り、パスワードを推測しようとするアルゴリズムを記述する必要があります。そのようなアルゴリズムが存在することを証明または反証できる場合、問題を解決しました。