NPは、多項式時間で解く方法が見つかっていないが、解が与えられたとき正しいかどうかを多項式時間で判定できる問題。Non deterministic Polynomial time。