Class
クラスP
「ある判定問題が多項式時間で計算するアルゴリズムを持つ時、その問題はクラスPに属する」ということ。
つまりは効率的に解くことができる問題のクラスです。
クラスとはそのような問題のかたまりといったイメージ
クラスNP
「ある判定問題の解となる入力が問題の条件を満たすかどうかを多項式時間で判定することができるようなアルゴリズムを持つ時、その問題はクラスNPに属する」ということ。
つまり、アルゴリズムは条件を満たす解を教えてもらえると、多項式時間でその解が正しいか確かめることができるが、自分で条件を満たす解を見つけるには指数時間かかる可能性があるという性質を持ちます。
ex.
・巡回セールスマン問題
・三彩色問題
一般的に、効率的に計算可能な関係（多項式時間アルゴリズム）$ \mathcal{R}が存在する場合、言語$ \mathcal{L}はクラスNPに属するという
$ \mathcal{L} = \lbrace x| \exist w, |w| \leq {poly(|{x}|) \wedge \mathcal{R}(x, w)} \rbrace
・効率的に計算可能な関係$ R={(x,w)∈F^n×F^h}
・NP言語$ L={x∈F^n∣∃w∈F^h,(x,w)∈R}
・$ x \in \mathcal{L}をステートメントといい、$ wを$ (x, w ) \in \mathcal{R}となる$ x \in \mathcal{L}を証明するための知識(witness)という
NP完全問題
クラスNPに属する問題のうち、解くのが最も難しい問題をNP完全問題と呼びます。