NE (complejidad)

En la teoría de la complejidad computacional , la clase de complejidad NE es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en tiempo${\displaystyle 2^{O(n)}}$. ^{[ 1 ]} Es similar a NEXPTIME , el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en tiempo${\displaystyle 2^{n^{O}(1)}}$. Por definición, está contenido en NEXPTIME .

NE , a diferencia de NEXPTIME , no es cerrado bajo reducciones de muchos a uno en tiempo polinomial .

• E (complejidad)