NP Non-deterministic Polynomial http://ja.wikipedia.org/wiki/NP 1. 非決定性チューリングマシンによって多項式時間で解くことができる問題。 2. yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。NPはPよ…