Diferencia entre revisiones de «Clase de complejidad»

*La clase [[NP_(clase de complejidad)|NP]] es el conjunto de problemas de decisión que pueden ser resueltos en [[tiempo polinómico]] por una [[máquina de Turing]] no determinista.

*La clase [[PSPACE]] es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en [[espacio polinómico]].

 

== Véase también ==