[1]
[[多項式時間]][[計算量]]の[[非決定性チューリング機械]]によって[[受理]]される[[言語]]全体の[[集合]]を、[DFN[[[クラス]][CODE(math)@en[[VAR['''NP''']]]]]]といいます。
([[名無しさん]] [sage])


[2]
'''定理''':
[CODE(math)@en[[VAR[L]] ∈ [VAR['''NP''']]]]は、
[[時間計算量]][CODE(math)@en[[VAR[k]][SUP[[VAR[P]] ([VAR[n]])]]]]
のある[[決定性]][[チューリング機械]]で受理される。
([[名無しさん]] [sage])