algorithm - NP-完全 VS NP-ハード

Question

NP-Complete と NP-Hard の違いを理解しようとしています。

以下は私の理解です

NP 困難な問題は、多項式時間では解けないが、多項式時間で検証できる問題です。
NP 完全問題は、NP 内にあり、NP 困難でもある問題です。

上記の定義は正しいですか？もしそうなら、NP ではなく NP-Hard の問題についてはどうですか。それらは NP 完全問題よりも難しくないでしょうか? 指数時間でしか解決および検証できないと言うのですか?

Answer 1

簡単にしましょう。

教授は学生に問題を与え、効率的なアルゴリズムを提供するように依頼します。

翌日、彼の知的な学生の何人かがアルゴリズムを解読して解決しました。O(2 ⁿ )の複雑さがあります。今では、解決策を得るアルゴリズムを手に入れたことに全員が満足しています。すべてが良さそうです。

教授は彼らを高く評価するが、「課題はまだ終わっていない」と言い、システムを使って実際に解決するように要求します。

そのため、彼らはすぐにシステムでそれをエミュレートしようとします。ある学生は、彼のシステムは 1 GIPS ( 1 秒あたり1000,000,000命令) という驚異的な速度を備えており、数分の 1 秒以内に問題を解決できると述べています。そのため、彼らはアルゴリズムをコーディングし、それを実行しようとします。

次に、データセットへの100 個の入力から開始し、それを実行します。彼らは、プログラムが実行され、実行され、実行され、停止しないことに驚きました。

次に、別の生徒が計算を行ったところ、システムが問題を解くのに2 ¹⁰⁰ / 10 ⁹秒かかることがわかりました。だいたい2 ～ ⁴⁰年くらい。

翌日、プログラムがまだ実行されている間に、教授は次のように述べました。そこにそれを見るために」 .

しかし、同じ問題でも、解を生成した後、現実的な時間で NP 困難な問題の解を検証できる場合、それはNP-Completeと呼ばれます。たとえば、サブセットの合計は NP 困難な問題です。しかし、部分集合の解が得られると、多項式時間で簡単に確認できます。したがって、NP-Complete になります。

Answer 2

NP-Hard の定義は正しくありません。複雑さクラス NP の (正確には正しくない) 定義に似ています。

複雑性クラス NP とは何ですか?

計算問題は、効率的に検証pできる場合、複雑性クラス NP に属します。複雑性理論では、多項式時間のかかる計算は効率的であると見なされます。したがって、形式的にifは多項式時間で検証可能です。p ∈ NPp

あなたの定義では、複雑度クラス P に対応する多項式時間可解という概念に言及しました。NP 完全問題は、P = NP の場合にのみ、多項式時間可解です。有名なP 対 NPは、コンピュータ サイエンスにおける最大の未解決問題の 1 つであることに注意してください。そのため、現在、P = NP なのか P ⊊ NP なのかは誰にもわかりません。であると広く信じられている）。

NP 困難な問題とは

直感的には、NP 困難な問題は、少なくとも NP の問題と同じくらい難しい計算問題です。p計算上の問題が少なくとも別の問題と同じくらい難しいと言うときq、実際には逆に考えます - 時間 T で解決できる場合、Tとほぼ同じ時間でp解決できるよりも(たとえば、多項式係数によって異なります) ）。q

より正確には、からへの多項式時間の削減がある場合、それpは少なくとも別の問題と同じくらい難しいと言います。大雑把に言えば、多項式時間削減とは、を解くアルゴリズムが与えられた場合、 を解くためにブラックボックスとして (つまり、 の時間計算量をとして扱う)を使用して多項式時間アルゴリズムを構築できることを意味します。qqpApBAAO(1)q

NP 困難な問題の場合、NP 困難な問題が多項式時間で解決できる場合、すべてのNP 問題は多項式時間で解決できます(したがって、P = NP!)。そのため、NP 困難な問題は多項式時間で解けないと広く信じられています。

NP完全問題とは？

あなたの質問で正しく述べたように、pそれが NP-Hardで p ∈ NP.

NP にない NP-Hard problem?

NP にない NP-Hard 問題が存在する場合 (私の知る限り、現時点でこのカテゴリに該当することが証明された問題はありません)、そのような問題は NP-Complete 問題よりも困難です。

証明:私たちの主張が正しくないとします。NP -Hard であるが NP ではない別の問題と少なくとも同じくらい難しいpNP-Complete 問題とします。は少なくとも と同じくらい難しいので、から への多項式時間の削減 (時間内に実行されるとします)があります。は NP であるため、 が多項式である時間のアルゴリズムによって検証できます。qpqP(n)qppAT(n)T

の任意のインスタンスが与えられた場合r、まずそれを のインスタンスに縮小し、次に を呼び出して検証することによりq、アルゴリズムを構築できます。は の多項式である時間で検証することに注意してください。 は NP であるということになり、矛盾が生じます!BspAsBqT(P(n))nq

Answer 3

NP-Hard は問題の下限です。不可能な問題も NP 困難です。NP-Complete は、NP-Hard であると同時に NP-Solvable であることを意味します。

多項式時間で検証できる問題は、NP の問題の定義の 1 つです。

Answer 4

あなたの定義はNP完全に対してのみ正しいです。

下から: P は、決定論的チューリング マシンによって多項式時間で解決できる問題のクラスです。NP は、非決定論的チューリング マシンによって多項式時間で解決できる (またはその解が多項式時間で決定論的チューリング マシンによって検証できる) 問題のクラスです。

NP 困難に関しては、次の特性を持つ決定問題 X を意味します。問題を解決するチューリング マシンが与えられた場合、多項式時間で NP の問題の任意のインスタンスを X のインスタンスに再構築 (チューリング縮約) できます。非公式に言えば、これは NP 困難な問題が「少なくとも NP と同じくらい難しい」問題であること、または X の解が NP のすべての問題に適用できることを意味します。問題が多項式時間で検証可能である必要はなく、実際に検証可能である必要もないことに注意してください。NP困難には、決定不能で認識できない問題も含まれます。

NP 困難に多項式時間で解ける問題 (P ?= NP 問題) が含まれているかどうかはわかりません。現在、NP 困難な問題に対する単一の多項式時間解は見つかっていませんが、そのような解が存在しないことも証明されていません。NP 困難な問題 X に対してそのような解が見つかった場合、それは P = NP を意味します。これは、NP の問題の任意のインスタンスを多項式時間で X のインスタンスに変換できるためです (NP 困難な問題のチューリング縮約特性のため)。 X の多項式時間解によって多項式時間で解かれます。