NP 类

$NTIME(t(n))=\{L|L\text{可被}O(t(n))\text{时间NTM判定}\}$

NP 类问题是单带非确定 TM 在多项式时间内可判定的问题, 即 $NP={\bigcup }_{k}NTIME(n^k)$.