NP
Non-deterministic Polynomial
http://ja.wikipedia.org/wiki/NP
1. 非決定性チューリングマシンによって多項式時間で解くことができる問題。
2. yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。
NPはPよりも大きいと予想されているが、証明されていない。P≠NP予想という。
NP完全
http://ja.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C
クラスNPに属する問題でかつ、クラスNPのすべての問題から多項式時間帰着可能な問題である。
すなわち、NPに属する問題のうちでNP困難なものである。
NP困難
http://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3
問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。
NP困難である問題はNPに属するとは限らない。
