1

決定問題 A があり、それが NP 完全であることを示したい場合。別の NP 完全問題が多項式で A に還元されることを証明するだけで十分ですか、それとも別の NP 完全問題が多項式で A に変換されることを示す必要がありますか?

つまり、それを示すことができますか

procedure solve_SAT
...
call solve_A
call solve_A
call solve_A
...
end

または、示されているように、solve_A の使用は 1 回だけに制限されていますか?

procedure solve_SAT
input  = ...
result = call solve_A(input)
return result
end

一部の情報源は前者を言い、他の情報源は後者を言っていることがわかり、少し混乱しています.

4

3 に答える 3

2

決定問題 A があり、それが NP 完全であることを証明したいとします。それを行う方法は、既存の NP 完全問題を取り、それを A に簡約することです。ここでの簡約とは、多項式時間簡約です。 .

したがって、3-SAT が NP 完全であることを示したい場合、SAT 問題からの還元を示すことができます。

ここで注意すべき重要なことは、リダクションはポリ時間でなければならないということです。solve_A() を複数回呼び出すかどうかは問題ではありません。solve_A() の多項式呼び出しを行う限り、solve_A() を複数回呼び出すことを選択できます。

なぜそれが機能するのですか？矛盾で証明できます。3SAT のポリタイム アルゴリズムがあるとします。次に、ポリタイムでもSATを解くことができます。多項式関数の呼び出しの多項式数は依然として多項式であるため。したがって、P=NP でない限り、SAT は 3SAT 用に新たに発見されたポリ時間アルゴリズムを使用して多項式時間でも解決できることを意味します。しかし、SAT が NP 完全であることはわかっているため、3SAT も NP 完全でなければなりません。

つまり、NP 完全性を示すには 2 つのことが必要です。

証明書の存在。既存の NP 完全問題からの削減。

于 2012-01-28T01:21:34.140 に答える
1

solve_SAT のプロシージャが solve_A の一定数の呼び出しのみを使用する場合、A の多項式時間アルゴリズムは、SAT の多項式時間アルゴリズムを意味します。これは SAT の正確な定義を満たしていませんが、P = NP でない限り、A の多項式時間アルゴリズムが存在しないことを意味します。

于 2011-09-13T19:54:54.647 に答える
0

現在確立されている NP 完全性の定義は、NP 完全性を示すには、既知の NP 完全問題から問題への多項式の多項式または Karp 簡約が必要であるというものです。これは多項式変換とも呼ばれ、 solve_A 関数を 1 回だけ呼び出す例に対応します。

solve_A を多項式回数呼び出すことができる他の例は、チューリングまたはクック削減に対応します。NP 完全問題からあなたの問題へのチューリング簡約の存在は、あなたの問題の NP 困難性の証明であり、これは NP 完全性とは異なる特性であると考えられています。

于 2012-01-27T05:20:53.060 に答える