すべてのNP完全な問題はどのように似ていますか？

Question

特定の問題がNP完全であることを証明するいくつかの証拠を読んでいます。プルーフテクニックには、次の手順があります。

1. 現在の問題がNPであることを証明します。つまり、証明書が与えられ、それが多項式時間で検証できることを証明します。
2. 既知のnp完全問題（「簡単」と呼びます）を取り、削減します すべてそのインスタンスの 少し 指定された問題のインスタンス（「ハード」と呼びます）。これはそうです いいえ 必然的に1：1マッピング。
3. 上記の削減は多項式時間で行うことができることを証明してください。

すべてここにあります。この知識は、「多項式時間でNP完全な問題を解決できる場合、すべてのNP完全な問題を多項式時間で解決できる」という正しいことでしょうか？

はいの場合、上記のプルーフテクニックに従って、「簡単な」問題は多項式時間で解決できると言ってみましょう。ここに何が欠けていますか？それとも、これは真実であり、その「難しい」問題も「簡単な」問題に減らすことができますか？

Answer 1

あなたの質問は、現在の問題が難しくないとすぐに確信していないという事実から来ているようです。現在の問題は、NPにあるため、NPコンプリートの問題よりも難しくありません。

NPの完了性の概念が存在することさえ確信したい場合（つまり、NPの不完全な問題に削減できる）ことを調査する必要があります。 クックレビン定理 SATはNP不完全であると述べています。

np-completenessは、 どれか NPの問題は、式として元の問題の検証者であるチューリングマシンをエンコードすることにより、証明が機能します。この式は、チューリングマシンを受け入れる入力が存在する場合にのみ満たします。原則として、この証明を使用して現在の問題をSATに減らし、その後、多項式時間削減の推移性を介して他のすべてのNP不完全な問題に還元することができます。

（私は実際にコメントでクックレビン定理へのリンクを追加したかっただけですが、これは私の最初のstackexchangeの投稿であり、まだコメントさせないと思います。）

Answer 2

削減の方向に混乱しています。それでは、議論する方法を説明させてください。

言語があり、たとえば$ l $を持っていて、それがnp完全であることを示したいと思います。最初に、良い証明書を見つけることにより、実際にNPにあることを示します。したがって、NPハードを表示することによって残されます。これは、いくつかのNP完了言語$ l_ Text {npc} $を減らすことで実行できます に あなたの言語$ l $、ポリタイムによる 多くの削減. 。これは、ポリタイム関数を定義することを意味します。$ l_ text {npc} $のyes-instances $ l $ of $ l $にマップし、$ l_ text {npc} $にno-instancesにマップすることを意味します。 $ l $の。

によって 推移性 ポリタイムの多くの削減のうち、NPのすべての言語は$ l $に減らすことができます（$ l_ text {npc} $を超えて迂回します）。一方、$ l $を決定する決定論的ポリタイムアルゴリズム$ a $が存在する場合、最初に$ l $に減らしてから$ a $を尋ねることにより、多項式時間にすべての言語を決定できます。

あなたは間違った方向に考えたばかりのようです。あなたが「簡単」と呼んだ問題は、削減とあなたが「ハード」と呼ぶ問題の助けを借りて解決することができます。まず第一に、これは奇妙な誤解を招く用語であり、第二に、それはおそらくその逆であるべきです。

Answer 3

セット$ a subset mathbb r $を与えられた場合、$ a $がセット$ a $の最大の要素であることをどのように示しますか？ 2つのステップがあります。

1. $ a in a $を示します。
2. $ b in a $、$ b leq a $の場合を示します。

$ a、b $がセット$ a $の最大の要素である場合、条件2を2回適用します（$ a $ and $ b $の場合）、$ a leq b leq a $を取得します。 $ mathbb r $では、これは$ a = b $を意味し、セットには最大の要素が1つしかないことを意味します。

---

ここで、$ mathbb r $を$ a^{ ast} $および$ leq $で置き換えます。 $ l $がnp完全であることを示すために、ステップがあります。

1. $ l in mathsf {np} $を示します。
2. $ l ' in mathsf {np} $、$ l' leq l $についてこの状態はNP-Hardnessと呼ばれます。

$ l、m $が2つのnp不完全言語である場合、条件2を2回適用すると、$ l leq m leq l $が得られます。つまり、問題は同等です。$ l $を解決できる場合は、$ m $を解くことができ、その逆もできます。実際とは異なり、$ l neq m $であることは事実かもしれません。 $ l sim m $平均$ l leq m leq l $とします。これが同等の関係であることを示すことができます。

---

エクササイズ。

$ m $がNP不完全であり、$ l sim m $であると仮定します。 $ l $がnp完全であることを示します。

1. $ l in mathsf {np} $を示します。

   $ m $はnpであり、$ l leq m $にあるため、$ l $を認識するマシンは削減を使用するだけです。

2. $ l ' in mathsf {np} $、$ l' leq l $について

   $ m $はnp-hard、$ l ' leq m $です。私たちは$ m leq l $を知っているので、トランジテーション$ l ' leq l $によって。

---

したがって、2つの言語がNP不完全である場合、それらは同等です。言語がNP完了言語に相当する場合、NP Completeでもあります。

Answer 4

ここには2つの誤解があるようです。

1. 「簡単」と「ハード」：どちらかといえば、それは逆です。与えられた問題は「簡単」です（その複雑さはわかりません）、もう1つは 知られています 難しい。
2. "減らす すべて そのインスタンスの 少し 指定された問題のインスタンス」：強調は誤解を招きます。削減の値の範囲がどれだけ大きいかは重要ではありません。中心は、削減がインスタンスがYESインスタンスであるかどうかを保持することです。つまり、NPC問題の例はYESインスタンスの削減画像が指定された問題のイエスインスタンスである場合にのみ。

次に、あなたがしていることは、与えられたインスタンス（多項式時間）のインスタンスにそのインスタンスをマッピングして、それらを解決することにより、困難な問題を解決できることを示すことです。したがって、困難な問題は与えられた問題よりも難しくありません。同様に、与えられた問題は少なくとも難しい問題と同じくらい難しいです。 quod erat decodandum。