問題X（決定問題）がNP完全であることがわかっていて、多項式時間で問題Yに還元されることが証明されている場合、問題YはNP完全であると言えますか？
私の最初の考えは、いいえ、問題YはそれがNPにあることを示す必要があるということでした。しかし、さらに考えた後、XがYに縮小された場合、YはすでにNP完全であると見なされます。今、私は混乱しています...どんな助けもいただければ幸いです。
5 に答える
1
コントラリウムごとの引数:
X ∈ NP かつ X ⇔ Y かつ Y ∉ NP の場合、X ∉ NP です。
于 2010-11-02T02:51:45.967 に答える
1
問題 X - 不明
問題 Y - NP 内
X が NP であることを証明するには、X のすべての問題を Y の問題に還元するための手順に従うことができることを示します。そうすれば、X の問題は、同等の Y の問題と少なくとも同じくらい難しいことがわかります。
いいえ、Y から始めて X に減らす必要があります。
于 2010-11-02T02:55:20.143 に答える
0
はい、そうです。多項式時間の問題を既知の NP 完全問題に減らすことができますが、それは非常に難しい作業と見なされます。したがって、代わりに、すでにNP完全な問題を選択してそれを問題に減らし、それがNPであることを示すと、問題はNP完全になります。
于 2013-12-01T00:00:25.250 に答える
0
まだ、いくつかの手順が必要です
問題 L が NP 完全であることを証明するには、次の手順を実行する必要があります。
- 問題 L が NP に属していることを証明します (つまり、解が与えられれば、多項式時間で検証できます)。
- 既知の NP 完全問題を選択 L'
- L' を L に変換するアルゴリズム f を説明してください
- あなたのアルゴリズムが正しいことを証明してください (正式には: x ∈ L' は f(x) ∈ L の場合のみ)
- algo f が多項式時間で実行されることを証明する
ここまでで、ステップ 2、3、4
が完了しました。削減が多項式であること (ステップ 5)
と、問題が NP に属していること (ステップ 1) を示す必要があります。つまり、解は多項式時間で検証できます。
于 2016-09-01T00:53:02.550 に答える
0
SAT は ALL への 1 回の呼び出しで解決できますが、それは ALL が NP にあるという意味ではありません。
于 2010-11-02T06:13:26.093 に答える