p-np - NP 完全に還元できるが、その逆はできない NP 問題の例は何ですか?

Question

NP完全問題に還元可能であるが、その逆ではないNP問題の例は何ですか? NP と NP-complete について読んだとき、マッピングは 1 対 1 になるので、それらを分類するのはばかげていると思いました。しかし、確かに一方向にしか還元できないという問題があります。私はそれらを知りたいと思っています。

Answer 1

すべての NP 問題は NP 完全問題に還元できます。NP 完全問題は、特殊なタイプの NP 問題です。したがって、NP 完全問題は、NP にあると見なすために簡約する必要はありません。彼らはすでにNPにいます。