コンピュータサイエンスにおけるNP完全とは何ですか? [closed] 質問する

とはNP?

NPはすべての集合である意思決定の問題（はいまたはいいえで答える質問）に対して、その「はい」の答えは多項式時間（O(n ^k )、ここでnは問題のサイズ、kは定数）で検証できる。決定論的チューリングマシン多項式時間は、速い、または迅速にという定義として使用されることがあります。

とはポ?

P は、決定論的チューリングマシンによって多項式時間で解決できるすべての決定問題の集合です。これらの問題は多項式時間で解決できるため、多項式時間で検証することもできます。したがって、P は NP のサブセットです。

とはNP完全?

NP に属する問題 x は、NP に属する他のすべての問題が x にすばやく (つまり、多項式時間で) 変換できる場合にのみ、 NP 完全でもあります。

言い換えると：

1. xはNPに属し、
2. NPにおけるあらゆる問題は還元可能なxに

したがって、NP 完全が非常に興味深いのは、NP 完全問題のいずれか 1 つがすぐに解決できれば、すべてのNP問題もすぐに解決できるということです。

投稿もご覧ください「P=NP?」とは何ですか? また、なぜそれが有名な質問なのでしょうか?

とはNP困難?

NP 困難とは、NP の最も難しい問題と少なくとも同じくらい難しい問題です。NP 完全問題も NP 困難であることに注意してください。ただし、NP接頭辞として が付いているにもかかわらず、NP 困難問題のすべてが NP (または決定問題) であるわけではありません。つまり、NP 困難の NP は非決定性多項式時間を意味するわけではありません。はい、これは紛らわしいですが、その使用法は定着しており、変更される可能性は低いです。