P NP-completeでないNPのすべての問題はありますか？

Question

1. P NP-completeでないNPの問題はすべてありますか？ 自分自身をより明確にするために、NP-P = NPCですか？そうでない場合は、NP問題であるNPとNP完全でない問題の例を挙げることができますか？

2. すべてのNP完全な問題はNP困難ですか？

ありがとうございます。私は間違いなく2

NP困難に答えることができ

Answer 1

は、その定義によると、NP完全のために必要とされます。 Hは、NPのすべての問題を多項式時間で問題にすることができれば、NP完全であると言われます。したがって、NP硬度の定義であるNPの他の問題を解決することであるので、少なくともHを解決することは難しいでしょう。

Answer 2

まず、絵

1. Problems in NP not known to be in P or NP-complete

それはラドナーで示されたものP ≠ NPは、どちらPもNP-completeであるNP に問題が存在する場合。このような問題は、 NP-intermediateという問題です。 graph isomorphism problem、discrete logarithm problemおよびinteger factorization problemは、NP-intermediateと考えられる問題の例 である。彼らは、非常に いくつかのNPPまたはNP-completeにあることが知られていない問題の一部です。

NP-hard

は、少なくともとしてハード NPにおける最も困難な問題のような問題のクラスです。したがって、はい、すべて NP-complete問題は NP-hardです。

Answer 3

最初の質問では、答えはP = NPであるかどうかによって決まります。 P = NPならば、NPにはPにない問題はないので、そのような問題は存在しない。一方、P ≠ NPの場合、Ladner's theoremと呼ばれる結果は、NPではなくPであり、NP完全ではない（これらはNP中間問題と呼ばれる）問題があることを保証する。この定理の証明は、すべての基準を満たす高度に考案された言語を構築することによって機能します。私たちはNP中間体である特定の問題について今は知らない。なぜなら、われわれが知っていれば、P ≠ NPであることが分かっていたからだ。

2番目の質問では、はい、すべてのNP完全な問題はNP困難です。 NP完全な問題は、クラスNPにもあるNP困難な問題であると定義される。