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

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

相关条目

编辑

参考资料

编辑