L (clase de complejidad)
clase de complejidad
En teoría de la complejidad computacional, la clase de complejidad L (LSPACE o espacio logarítmico 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 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
P es diferente de NP o bien NP es diferente de PSPACE, pero no se sabe cuál de las dos inclusiones es propia.
Véase también
🔥 Top keywords: Wikipedia:PortadaLamine YamalEurocopaNico WilliamsShannen DohertyCarlos AlcarazMarc CucurellaEspecial:BuscarNovak DjokovicRodri HernándezLuis de la Fuente CastilloDani OlmoCopa AméricaÁlvaro MorataSelección de fútbol de EspañaRobin Le NormandEurocopa 2024Cleopatra I de EgiptoDonald TrumpRichard Ríos MontoyaMikel OyarzabalDani CarvajalIñaki WilliamsHarry KaneEstadio Olímpico de BerlínAymeric LaporteGrand Slam (tenis)Jesús NavasClaudio ReyesRafael NadalCopa América 2024Selección de fútbol de InglaterraCampeonato de WimbledonEurocopa 2020Copa Mundial de FútbolCopa América 2001Unai SimónNéstor LorenzoLuke Perry