L (complexity)
Complexity class (logarithmic space) / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about L (complexity)?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
"Logspace" redirects here. Not to be confused with Logscale.
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space.[1][2] Formally, the Turing machine has two tapes, one of which encodes the input and can only be read,[3] whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input[1] and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way.