NP Complete の正式な定義を理解しようとしていますが、いくつか質問がありました。誰かがより多くの洞察を提供できるかどうか疑問に思っていました。
Jon Kleinberg アルゴリズムの本では、すべての NP 問題を問題 X に還元できる場合、問題 X は集合 NP 完全に含まれると述べています。
P は NP のサブセットであるため、P の問題を多項式時間で NP 完全問題に還元できることになります。これは、リダクションが多項式時間で行われるため、この NP 完全問題を多項式時間で解くことができるという矛盾につながります。これは真実ではありません。したがって、この推論のどこが間違っているのかわかりません。
また、多項式時間で NP 問題を NP 完全に還元できるのであれば、なぜ NP 完全が難しいと言えるのでしょうか。リダクションは多項式時間で行われるため、漸近的に言えば、違いはありません。