NP
Non-Deterministic Polynominal Timeの略。有名な勘違いだがNon-Polynominalではない。非決定性チューリングマシンによって多項式時間で解くことができる問題のクラス。別の定義では、解が与えられたときに多項式時間で検証可能な問題のこと(
https://ja.wikipedia.org/wiki/NP
)。
有名なNP問題としては巡回セールスマン問題や3-SATがある。