-1

サブセット問題はウィキペディアで次のように定義されています。

整数の集合が与えられたとき、合計がゼロである空でないサブセットはありますか? たとえば、セット { −7, −3, −2, 5, 8} が与えられた場合、サブセット { −3, −2, 5} の合計はゼロになるため、答えはイエスです。

また

整数の集合と整数 s が与えられたとき、合計が s になる空でないサブセットはありますか?

この問題のブルート フォース ソリューションは指数関数的です (N 個の数のすべてのサブセットを循環し、それらのすべてについて、サブセットの合計が正しい数になるかどうかを確認します)。指数時間で実行されるブルート フォース用に最適化されたバージョンもあります。

2 次と多項式の時間計算量の間で総当たり解 (上記の質問に対する正確な解) を計算できるアルゴリズムがあるとします。

P=NP の問題、時間の複雑さなどに関連してどのように考えられるでしょうか?

アルゴリズムが存在すると仮定すると、サブセット合計問題の最先端の改善になるでしょうか?

（私はこの分野の専門家ではないので、何かが意味をなさない、または明確でない場合は、できる範囲でこの質問に追加の情報を提供します:)）

4

1 に答える 1

2

サブセット問題は NP 完全であるため、問題の多項式時間解を見つけることができれば、NP のすべての問題を多項式時間で解くことができ、P = NP となります。

さて、もちろん、上記のステートメントは、NP と NP 完全性が何であるかを理解しないと意味がありません。NP 問題を定義するには多くの方法がありますが、最も簡単な方法は、多項式時間で解の正しさをチェックできる検証者が存在する場合にのみ、問題が NP にあるということです。部分集合和問題の場合、多項式時間で解を検証できることは明らかです。したがって、これは NP 問題です。

クラス NP-complete は、NP のすべての問題を多項式時間で NP-complete の任意の問題に還元できるような NP の特別な問題のセットです。例として、Cook によって最初に証明された NP 完全問題は SAT 問題です。この問題では、ブール式が true と評価されるように、ブール変数のセットへの可能な割り当てが存在するかどうかを判断しようとします。正しい手順を使用すると、NP のすべての決定問題を多項式時間で SAT に変換できます。これにより、SAT は NP 完全になります。元の証明の詳細については、こちらを参照してください。ただし、チューリング マシンについての理解が必要です。

新しい問題の NP 完全性を証明するために、既存の NP 完全問題を新しい問題に還元することができます。例として、SAT 問題は簡単に 3-SAT 問題に還元できることがわかっています。これは、与えられた SAT 問題を 3-SAT バージョンに変換して、同等の 3-SAT 問題を解くと元の SAT 問題の結果が得られることを意味します。NP のすべての問題は SAT に還元でき、SAT は 3-SAT に還元できるため、3-SAT 問題は NP 完全になります。

これは、3- SATを部分和の問題に還元する方法の優れた証明です。証明の結果、部分和問題は NP 完全です。したがって、サブセット合計問題の多項式時間解を見つけることができれば、すべての NP 問題 (はい、巡回セールスマン、グラフの色付け、ナップザックなどの問題を含む) を多項式時間で解くことができます (すべての削減は多項式時間で行われます)。

于 2013-07-10T01:07:52.620 に答える