NE (复杂度)

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

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

相关条目

• E (复杂度)

参考资料

• Complexity Zoo: NE.