免責事項：私は現在、データサイエンスブートキャンプの学生ですが、まだアルゴリズムに慣れていません。 これは私が自分の時間にいくつかの研究をしている間につまずいただけのものです。 それは興味深い話題だと思った。 レコード店ディスクユニオンプロや経験のアルゴリズムでていない。 うまくいけば、私はすぐになりま
私の基本的な理解から、これらの用語はすべてアルゴリズムのBig-O表記を扱っていると信じています。 今、私はカバーできることは非常に分かりやすくお伝えします.,
要約すると、Big-Oは、アルゴリズムがどれだけ速く実行されたか、または問題を解決したかの尺度です（実行時間の上限であることに注意してください）。P、NP、NP-Hard、およびNP-Completeは、問題が該当するか、または分類されるクラスです。
P(Polynomial)problems
P問題とは、アルゴリズムが解くのに多項式時間を要する問題、またはBig-Oが多項式である問題（つまり、O(1)、O(n)、O(n2)など）を指します。 これらは解決が”簡単”であると考えられる問題であり、したがって一般に膨大な実行時間を持たない。,
NP（非決定性多項式）問題
NP問題は私が理解するのが少し難しかったですが、これが彼らのものだと思います。 NP問題を解くという点では、実行時間は多項式ではありません。 それは次のようなものになりますO(n!）またははるかに大きな何か。 しかし、このクラスの問題は特定の解を与えることができ、解をチェックすると多項式実行時間が得られます。 私がこれを少しよく理解するのを助けた例は、数独ゲームでした。,
このパズル全体を解決するためには、アルゴリズムは各3×3行列をチェックして、どの数字が欠落しているか、各行、各列、そして0-9の数字の繰り返しがないことを確認する必要があります。 これは、欠けている桁数が各行、列、および行列で矛盾しているため、より複雑になります（つまり、左上の行列は4桁が欠落しているのに対し、右上の行列は8桁が欠落しているためです）。 この問題を解決するには、多項式実行時間はありません。, ただし、このパズルに可能な解決策を提供する場合は、行、列、および行列に繰り返しがあるかどうかを確認するのははるかに複雑ではありません。 これは、多項式の実行時間を持つ単純なチェックです。
本質的に、NPクラスの問題には解決する多項式の実行時間はありませんが、解を検証する多項式の実行時間があります（解決が難しく、与えられた答えをチェックするのは簡単です）。
還元
私は実際に例を使用しての外でこれを説明することはできませんので、：私たちは二つの問題、AとBを持っており、我々は問題BがPクラスの問題であることを知っています。, 問題Aを減らすことができ、または問題Bに変換することができ、この還元に多項式時間がかかる場合、AもPクラス問題であると言うことができます（AはBに還元可能です）。
この概念は、他の二つのクラスの問題について理解することが重要です。
NP困難な問題
問題は、それを解くためのアルゴリズムがNP問題を解くために変換できるとき、NP困難に分類されます。 それから、この問題は少なくともNP問題と同じくらい難しいと言うことができますが、はるかに難しいか複雑になる可能性があります。,
NP完全問題
NP完全問題は、NPおよびNPハードクラスの両方に存在する問題です。 これは、NP完全問題は多項式時間で検証でき、任意のNP問題は多項式時間でこの問題に還元できることを意味します。
以下は、異なるクラス空間のベン図です。,
うまくいけば、これはこのトピックについてのことをクリアすることができます。 明らかに、私は非常に限られた知識を持ってい 私はちょうどこれについて話すのが面白いと思っていましたが、高いレベルでさえ、これはかなり混乱しているようです。