NP 是具有多项式验证者的语言集合。等价地,NP 是可以用一个非确定性 Turing 机在多项式时间内判定的问题的集合。
NP=k⋃NTIME(nk)
与 P 复杂度类一样,NP 对合乎情理的非确定性计算模型是不变的。
定义 coNP 是所有补集在 NP 中语言的集合。
验证者
称一个语言 A 的验证者是 V,如果
A={w∣V accepts ⟨w,c⟩ for some string c}
多项式时间验证者是能在 ∣w∣ 的多项式时间内完成验证的验证者。显然,这要求其中的 c,也称凭证,的长度必须是多项式的。
称一个语言是多项式可验证的,如果它有一个多项式时间的验证者。
相关内容
NP 和 P 复杂度类的大小关系目前还不清楚。但是可以知道
NP⊆EXPTIME=k⋃TIME(2nk),
参考文献