ある問題を解く際に その問題がどのぐらい複雑なのかを示す指標として
P、NP、NP完全、NP困難 に分類されます。
Pの定義では、
「判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。」
二値分類や n * m の組み合わせを使って答えを求める問題は Pに該当する。
しかし、n ^ m の組み合わせを解くような問題は 現実的に解けないので Pとは言えない
対して NPはの定義は、
「非決定性チューリングマシンによって多項式時間で解くことができる問題」かつ、
「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」。
この辺りになると 量子コンピューターで解けるのではないかと言われている。
自分の読んでいても 理解ができませんでした。
比較的 わかりやすいと思ったサイトです。
初心者が学ぶP,NP,NP困難(Hard),NP完全(Complete)とは（わかりやすく解説）
