cOMPLEJIDAD COMPUTACIONAL

En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turingdeterminista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n.
Como ejemplos de problemas EXPTIME-completos están el buscar a partir de una posición (en una versión generalizada) delAjedrez, Damas, o Go y determinar si el primer jugador tiene una secuencia de jugadas ganadora a partir de allí. Estos juegos son EXPTIME-completos dado que las secuencias de jugadas a partir de unaconfiguración dada es exponencial sobre el tamaño del tablero. (Cuando se tiene un juego generalizado en el cual el número de jugadas a partir de una configuración es polinómico en el tamaño del tablero, elmismo problema resulta generalmente PSPACE-completo.)
En teoría de la complejidad computacional, la clase de complejidad 2-EXPTIME (a veces llamado 2-EXP) es el conjunto de todos los problemas dedecisión que pueden resolverse por una máquina de Turing determinista en O (2 2 p (n)) tiempo, donde p (n) es un función polinómica de.
Sin embargo, los teoremas de jerarquía temporal no proporcionanmedios para relacionar la complejidad determinista y la no determinista, y tampoco la complejidad espacial y temporal, por lo que no iluminan sobre las grandes cuestiones pendientes de la teoría de lacomplejidad computacional: Si P y NP, NP y PSPACE, PSPACE y EXPTIME, o EXPTIME y NEXPTIME son iguales o no.
P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY


Complejidad espacial

Sedefine el coste o complejidad espacial de un algoritmo como cantidad de memoria requerida (suma total del espacio que ocupan las variables del algoritmo) antes, durante y después de su ejecución

Enteoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio de polinomios () y...