bugfix> complexity-theory > 投稿

PまたはNPにある問題XをNP完全に縮小できる場合、その問題Xは自動的にNPハード問題ですか?

回答 1 件
  • 素早い返信: いいえ、違います。

    NPハード問題の定義を思い出してください。

    A problemXis NP-Hard if every problem in NPcan be polynomially reduced toX.

    一方、問題がある場合バツ 多項式に縮小することができます NP完全な問題Y、 だということだY 少なくとも同じくらい難しいバツ、 その逆ではありません。

    最後に、NP完全問題の場合Z 多項式に縮小することができますバツ、それから確かにバツ すべての問題としてNP困難ですW NPではZ そして、2つの削減を組み合わせることで、削減できますW にバツ、したがって、定義は満たされています。

    Q: PまたはNPにある問題XをNP完全に縮小できる場合、その問題Xは自動的にNPハード問題ですか?

    A: 番号

    Q: PまたはNPにある問題XがNP完全問題をそれに還元できるようなものである場合、その問題Xは自動的にNPハード問題ですか?

    A: はい

あなたの答え