参考
複雑性クラス
複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。
抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長）
例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えばFP）。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
P、NP、NP Complete、NP Hard のざっくりとした理解を目標にします。
P
計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
P は Polynomial 多項式を表します。
P問題とは「 多項式時間で解ける問題」です。
以前の投稿で、「準線形 Linearithmic」時間を実用的なアルゴリズムの基準として考えましたが、複雑性のクラス分けを考える時には、「多項式 Polynomial」時間を基準にします。
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ＮP は Non-deterministic Polynomial 非決定性多項式を表します。
非決定性とは
以下が分かりやすかったです。
「非決定性」とは、「2つの選択肢を同時に実行してどちらか一方で最終的に答えに到達できれば良い」というような意味合いです。
NP 問題は、「 非決定性チューリングマシン（≈非決定性オートマトン）によって多項式時間で解くことができる問題」のことです。
また、 NP 問題は、 「多項式時間で正解が本当に正しいかを判定できる問題」 と表すことができます。
「 非決定性チューリングマシン（≈非決定性オートマトン）によって多項式時間で解くことができる問題」 が「多項式時間で正解が本当に正しいかを判定できる問題」と同値になるのは、「 非決定性チューリングマシンが非決定的に正解を選択することで多項式時間で問題を解くことができるから」です。
「 多項式時間で解ける問題」 であるPは、 「多項式時間で正解が本当に正しいかを判定できる問題」 であるNPに含まれます。
P≠NP予想
P≠NP予想（P≠NPよそう、英: P is not NP）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
前述の流れで、\(P \subseteq NP \) となりますが、 \(P \subset NP \) なのか \(P = NP \) なのか、どちらかは分かりません。
良く例として出されるのが、素因数分解です。
素数をそれぞれ、\(p\)、\(q\)としその積を\(N\)とします（\(N = p \times q \) ）。
素数である \(p\)、\(q\) から\(N\) を求めるのは簡単で、Pクラスの問題です。また、 \(N = p \times q \) が正解かどうかを判定するのも多項式時間内で終了し、この問題は、PクラスかつNPクラスの問題です。
逆に、 \(N\) から素因数である \(p\)、\(q\) を多項式時間で求めるアルゴリズムは見つかっていません。しかし、「 \(N\) の素因数は \(p\) である」 ことは簡単に判定できます。 \(N\) の素因数分解は、 「NPクラスではあるが、Pクラスではない」であろう問題と考えることができます。
多項式時間変換
NP Complete、NP Hard の前に、「多項式時間変換」という概念を理解します。
ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」という。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ある問題Bを解くアルゴリズムをサブルーチンとして用いることで、問題Aを多項式時間で解くことができれば、問題Aは問題Bに多項式時間変換可能であるといいます。
NP Complete、NP Hard とも、「任意のクラスNPに属する問題から多項式時間変換可能である」問題です。
NP Complete・ NP Hard
NP Complete
NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
「任意のクラスNPに属する問題から多項式時間変換可能である」問題 のうち、クラスNPに属するものです。
NP Hard
NP困難（エヌピーこんなん、英: NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである[1]。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
「任意のクラスNPに属する問題から多項式時間変換可能である」問題、全ての集合です。
\(NP Complete \subset NP Hard \) です。
NP Complete や NP Hard が重要なのは、P≠NP予想を考えるときに、NP Completeな問題を多項式時間で解くアルゴリズムを見つけることできれば P=NP を証明できるからだと思います。
