En teoría de la complejidad computacional, la clase de complejidadNL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing no determinista tal que la solución, si existe, es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. Como NL también está contenida estrictamente en PSPACE, se concluye que en la relación
NL es diferente de PSPACE, pero aparte de eso es posible por cada inclusión que las clases sean iguales o no.
Datos:Q12857599
Septiembre 21, 2021
clase, complejidad, teoría, complejidad, computacional, clase, complejidad, espacio, logarítmico, determinista, conjunto, problemas, decisión, pueden, resueltos, espacio, contar, tamaño, entrada, donde, tamaño, entrada, máquina, turing, determinista, solución,. En teoria de la complejidad computacional la clase de complejidad NL espacio logaritmico no determinista es el conjunto de los problemas de decision que pueden ser resueltos en espacio log n sin contar el tamano de la entrada donde n es el tamano de la entrada por una maquina de Turing no determinista tal que la solucion si existe es unica La clase L esta contenida en NL y esta contenida estrictamente en PSPACE Como NL tambien esta contenida estrictamente en PSPACE se concluye que en la relacion L N L P N P P S P A C E displaystyle L subseteq NL subseteq P subseteq NP subseteq PSPACE NL es diferente de PSPACE pero aparte de eso es posible por cada inclusion que las clases sean iguales o no Datos Q12857599Obtenido de https es wikipedia org w index php title NL clase de complejidad amp oldid 119484009, wikipedia, wiki, leyendo, leer, libro, biblioteca,
