跳转到内容

NE (复杂度)

维基百科,自由的百科全书

计算复杂度理论内,复杂度类 NE是一个决定型问题的集合,包含能使用非决定型图灵机,在O(kn) (k是某个常数)时间内解决的问题。

NE与相近的类别NEXPTIME不同,在多项式时间多对一归约时并不封闭。

相关条目

参考资料