英文
NP class
简介
一种特殊的类.是由不确定型图灵机在多项式时间内接受的语言类.设NM为一个不确定型图灵机，p为一个多项式，如果对任何字W输入到NM后，需要NM接受W，那么总有一种接受的计算路径，其长度不超过p(|W|)步.换言之，NM的(非确定型)时间复杂性函数
ΦNM(n)≤p(n)(对任何n∈ω).
则称NM为具多项式时间界(p)的非确定型图灵机，p称为其界函数.所有由具有多项式时间界的非确定型图灵机所接受的语言组成之类记为NP，即NP={L|存在非确定型图灵机NM接受L & NM为具多项式时间界的}，称之为NP类.NP类反映了“多项式时间可验证性”这一概念.例如，对L∈NP，若W∈L，则总可在多项式时间内加以验证，但是尚不知道这种“多项式时间可验证性”与“多项式时间可计算性”是否一致，这就是著名的P=?NP问题.此外，NP类也是不依赖于任何具体地计算模型的一个语言类.