algorithm - P 対 NP の明確化

Question

ウィキペディアから引用された P vs NP 問題は、アルゴリズムの時間的複雑性に関するもので、「... は、コンピューターで解決策を迅速に検証できるすべての問題が、コンピューターでも迅速に解決できるかどうかを尋ねます。」

「問題の検証」と「問題の解決」の違いがここにあることを誰かが明確にしてくれることを願っています。

Answer 1

「問題の検証」と「問題の解決」の違いがここにあることを誰かが明確にしてくれることを願っています。

「問題の検証」ではなく、「解決策の検証」です。たとえば、与えられたセットがSATに対して有効かどうかを多項式時間でチェックできます。そのようなセットの実際の生成は NP ハードです。ウィキペディアの記事 NP (complexity) のVerifier-based definitionセクションが少し役に立ちます。

検証者ベースの定義

検証者ベースのNPの定義を説明するために、部分集合和の問題を考えてみましょう:これらの整数の合計がゼロになるかどうか。この例では、整数 {−3, −2, 5} の部分集合が合計 (−3) + (−2) + 5 = 0 に対応するため、答えは「はい」です。総和がゼロの部分集合が存在することを部分集合和問題と呼びます。

アルゴリズムに入力する整数の数が増えると、サブセットの数が指数関数的に増加し、実際、サブセット和の問題はNP完全です。ただし、特定のサブセット (証明書と呼ばれることが多い) が与えられた場合、サブセットの整数を合計するだけで、サブセットの合計がゼロかどうかを簡単にチェックまたは検証できることに注意してください。したがって、合計が実際にゼロである場合、その特定のサブセットは、答えが「はい」であるという事実の証明または証人です。特定のサブセットの合計がゼロかどうかを検証するアルゴリズムは、検証者と呼ばれます。問題はNPにあると言われています多項式時間で実行される問題の検証者が存在する場合にのみ。サブセット和問題の場合、検証者は多項式時間のみを必要とします。そのため、サブセット和問題はNPにあります。

グラフ理論に詳しい場合、ハミルトン サイクルは NP 完全問題です。与えられた解がハミルトン サイクル (線形複雑さ、解パスをたどる) であるかどうかを確認するのは簡単ですが、P != NP の場合、問題を解く多項式実行時間を持つアルゴリズムは存在しません。

おそらく、この文脈では「速い」という用語は誤解を招く可能性があります。O(n)最悪の場合のランタイムがやなどの多項式関数によって制限されている場合にのみ、アルゴリズムはこの点で高速ですO(n log n)。異なる順列があるため、長さのある特定の範囲のすべての順列の作成はn制限されませんn!。これは、問題がn ¹⁰⁰ log nで解決できることを意味します。これには非常に長い時間がかかりますが、それでも高速であると見なされます。一方、TSP の最初のアルゴリズムの 1 つは O(n!) で、もう 1 つは O(n ² 2 ⁿ ) でした。そして、多項式関数と比較して、これらのものは非常に速く成長します。

Answer 2

RSA 暗号化では、次のような素数が使用されます。2 つの大きな素数 P と Q (それぞれ 200 ～ 400 桁) が乗算されて、公開鍵 N が形成されます。N=P*Q 暗号化を破るには、与えられた N から P と Q を計算する必要があります。 P と Q は非常に難しく、何年もかかることがあります。解を検証するには、P に Q を掛けて N と比較するだけです。そのため、問題を解くのは非常に困難ですが、解を検証するのに何もかかりません。

PS例は、この質問のために簡略化されたRSAの一部にすぎません。実際の RSA はもっと複雑です。