私たちは、最短経路、オイラーグラフ、最小スパニングツリーなどの複雑な問題を解決するための効率的なアルゴリズムについ これらはすべてアルゴリズム設計者の成功事例でした。 この記事では、コンピュータサイエンスの失敗の話について議論します。すべての計算問題はコンピュータで解決できますか？
無制限の時間であってもアルゴリズムでは解決できない計算問題があります。 たとえば、Turing Halting problem（プログラムと入力が与えられた場合、その入力で実行されたときにプログラムが最終的に停止するのか、永遠に実行されるのか）。 アラン-チューリングは、すべての可能なプログラム-入力ペアに対する停止問題を解くための一般的なアルゴリズムは存在できないことを証明した。 証明の重要な部分は、チューリングマシンがコンピュータとプログラムの数学的定義として使用されたことです（ソース停止問題）。
NP完全問題の状態は別の失敗の話であり、NP完全問題は、その状態が不明である問題です。 NP完全問題に対して多項式時間アルゴリズムはまだ発見されておらず、それらのいずれに対しても多項式時間アルゴリズムが存在しないことを証明することはまだ誰もできていない。 興味深いのは、NP完全問題のいずれかが多項式時間で解くことができれば、それらのすべてを解くことができるということです。NP、P、NP完全、NP困難な問題とは何ですか？
Pは、決定論的チューリングマシンによって多項式時間で解くことができる問題の集合です。NPは、非決定性チューリングマシンによって多項式時間で解くことができる決定問題の集合です。 PはNPのサブセットです（多項式時間で決定論的な機械で解くことができる問題は、多項式時間で非決定論的な機械で解くこともできます）。
非公式には、NPは、与えられた選択肢の中で常に正しい推測を行う魔法のアルゴリズムである”幸運なアルゴリズム”を介して多項式時間で解くことができる決定問題の集合である（出典参照1）。NP-完全問題はNP集合の中で最も難しい問題です。
NP-完全問題はNP集合の中で最も難しい問題です。 決定問題LがNP完全であるとは、次のことを意味します。:
1）LはNPにあります（NP完全問題の任意の解は迅速に検証できますが、効率的な既知の解はありません）。
2）NPのすべての問題は多項式時間でLに還元可能です（還元は以下で定義されます）。
上記のプロパティ2に従う場合、問題はNP困難であり、プロパティ1に従う必要はありません。 したがって、NP完全集合はNP困難集合の部分集合でもある。決定問題と最適化問題
NP完全性は決定問題の領域に適用されます。
決定問題と最適化問題
NP完全性は決定問題の領域に適用されます。 最適化問題よりも意思決定問題の難易度を比較する方が簡単であるため、このように設定されました。 しかし、実際には、決定問題を多項式時間で解くことができることは、（決定問題への多項式の呼び出しを使用して）対応する最適化問題を多項式時間で解 したがって、決定問題の難しさを議論することは、多くの場合、最適化問題の難しさを議論することと本当に同じです。 （出典資料2）。
例えば、頂点被覆問題（グラフが与えられた場合、すべての辺をカバーする最小サイズの頂点集合を見つける）を考えてみましょう。 これは最適化の問題です。 対応する決定問題は、無向グラフGとkが与えられた場合、サイズkの頂点カバーがありますか？削減とは何ですか？
L1とL2を二つの決定問題とする。 アルゴリズムA2がL2を解くとします。 つまり、yがL2の入力である場合、アルゴリズムA2はyがL2に属しているかどうかに応じてYesまたはNoと答えます。
アイデアは、アルゴリズムA2がL1を解くためのアルゴリズムA1の一部になるように、L1からL2への変換を見つけることです。
一般的に学習の削減は非常に重要です。 たとえば、特定の問題を解決するライブラリ関数があり、新しい問題を解決した問題の1つに減らすことができれば、多くの時間を節約できます。 パスの積がパスに沿ったエッジの重みの乗算である特定の有向グラフで最小積パスを見つけなければならない問題の例を考えてみましょう。 最短経路を見つけるためのDijkstraのアルゴリズムのコードがあれば、この新しい問題の新しいコードを書くのではなく、すべての重みのログを取り、Dijkstraのアルゴ与えられた問題がNP完全であることを証明するにはどうすればよいですか？
NP完全の定義から、問題LがNP完全であることを証明することは不可能であるように見えます。 定義上、NPのすべての問題がlに多項式時間還元可能であることを示す必要があります。 このアイデアは、既知のNP完全問題を取り、それをLに減らすことです。 多項式時間の還元が可能であれば、還元の推移性によってLがNP完全であることを証明することができる（NP完全問題が多項式時間でLに還元可能であれば、すべての問題は多項式時間でLに還元可能である）。NP完全であることが証明された最初の問題は何でしたか？
NP完全問題の定義によって証明された最初のNP完全問題がなければなりません。 SAT（Boolean satisfiability problem）は、Cookによって証明された最初のNP完全問題です（証明についてはCLRSの本を参照）。エンジニアにとってもNP完全性について知ることは常に有用です。 あなたの会社のための非常に重要な問題を解決するために有効なアルゴリズムを書くように頼まれることを仮定しなさい。 多くの思考の後、あなたは現実的ではない指数関数的な時間アプローチを考え出すことができます。 あなたがNP完全性について知らないならば、あなたは私が効率的なアルゴリズムを使うことができなかったと言うことができるだけです。 NP完全性について知っていて、問題がNP完全であることを証明すると、多項式時間解が存在する可能性は低いと誇らしげに言うことができます。 可能な多項式時間解があれば、その解は多くの科学者が何年も試みてきたコンピュータサイエンスの大きな問題を解決します。私たちはすぐに、より多くのNP完全問題とNP完全性の証明について議論します。