NP完全
P=NP 問題のキーになる概念
https://gyazo.com/1de7627f4dc47ab3a61104c0ac5d8943
$ \mathcal{P}\neq\mathcal{NP}の場合の NP 関連用語のベン図
図では$ \mathcal{N}\neq\mathcal{NP}となっているが、きっと誤植
初心者が学ぶP,NP,NP困難(Hard),NP完全(Complete)とは（わかりやすく解説）
非決定的チューリングマシンを用いると多項式時間で解が得られる問題のクラスを NP (Nondeterministic Polynominal Time) 問題という
Not P ではない
多項式時間で～: 雑に言うと「簡単に解ける」
なお、問題と回答が与えられた場合の答え合わせは決定的チューリングマシンで多項式時間でできる
非決定的チューリングマシンが最適なものを選ぶのと同様に、答えまでの経路を最初から知っている状態で決定的チューリングマシンを動作させられるため
決定的チューリングマシンを用いると多項式時間で解が得られる問題のクラスを P (Polynominal Time) 問題という
P の問題は非決定的チューリングマシンを使うと多項式時間で解けるので、$ \mathcal{P}\subset \mathcal{NP}
ここで、今のところ決定的チューリングマシンでは多項式時間で解く方法が知られていない、「難しい問題」の集合が存在する
解けないと証明されたわけではないので「知られていない」だけ
解けないと証明されたら$ \mathcal{P}\neq\mathcal{NP}の証明になる
だから、「解けない」って言ってるやつは嘘つき。鼻が伸びろ。
この難しい問題の集合をNP困難 (NP-hard) という
少なくとも NP 以上に難しく、P以下に簡単ではないだろうという感じ
(ここで、「だろう」をつけないと嘘つき。鼻が伸びろ。)
NP 困難の中には NP にすら含まれず更に外側のクラスに属する問題も存在する。
そういう問題は決定的チューリングマシンでは多項式時間で解けないことが証明されていることがある。
NP 問題の中に NP-hard な問題が含まれており、これを NP 完全 (NP Complete) な問題という
やつは NP の中でも最強…！きっと決定的チューリングマシンには多項式時間では解かれないさ…！
図の中で NP の中に P でも NP 完全でもない領域が存在するが、これは「よく分かっていない」問題
多項式時間で解けるアルゴリズムは発見されていないが、NP 完全である証明もされていない問題
素因数分解の問題はその例
暗号論において素因数分解の困難性を仮定しているが、これは証明されていない