E S T _
T _ _ N _
L _
M _ S M _
P _ T _ N C _ _
C _ M P _ T _ C _ _ N _ L
Q _ _
_ N _
M _ Q _ _ N _
_ N _ V _ R S _ L
D _
T _ R _ N G ,
_ S _
Q _ _
_ L
J _ _ G _
D _
L _
V _ D _
_ S
T _ N
P _ T _ N T _
C _ M _
_ N
_ R D _ N _ D _ R
C _ N
M _ M _ R _ _
_ L _ M _ T _ D _ :
P _ R
_ L L _
_ S
T _ R _ N G - C _ M P L _ T _ . Clue
EN COMPLEJIDAD COMPUTACIONAL, LA CLASE DE COMPLEJIDAD E ES EL CONJUNTO DE PROBLEMAS DE DECISIÓN QUE PUEDEN SER RESUELTOS POR UNA MÁQUINA DE TURING DETERMINISTA EN TIEMPO 2O(N), Y ES POR LO TANTO IGUAL A LA CLASE DE COMPLEJIDAD DTIME(2O(N)). EN TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL, LA CLASE DE COMPLEJIDAD NTIME(F(N)) ES EL CONJUNTO DE LOS PROBLEMAS DE DECISIÓN QUE PUEDEN SER RESUELTOS EN UNA MÁQUINA DE TURING NO DETERMINISTA EN TIEMPO O(F(N)) Y ESPACIO ILIMITADO. ESTO TIENE LA MISMA POTENCIA COMPUTACIONAL QUE UNA MÁQUINA UNIVERSAL DE TURING, ASÍ QUE EL JUEGO DE LA VIDA ES TAN POTENTE COMO UN ORDENADOR CON MEMORIA ILIMITADA: POR ELLO ES TURING-COMPLETO. DESDE UN PUNTO DE VISTA TEÓRICO, ES INTERESANTE PORQUE ES EQUIVALENTE A UNA MÁQUINA UNIVERSAL DE TURING, ES DECIR, TODO LO QUE SE PUEDE COMPUTAR ALGORÍTMICAMENTE SE PUEDE COMPUTAR EN EL JUEGO DE LA VIDA.