L (complexity)

<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, L (also known as LSPACE, LOGSPACE or DLOGSPACE) is the <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> containing <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> that can be solved by a <a href="/facts/Deterministic_Turing_machine/ojCtglYu">deterministic Turing machine</a> using a <a href="/facts/Logarithm/QeXaV97q">logarithmic</a> amount of writable <a href="/facts/Memory_space_(computational_resource)/YyleNx71">memory space</a>. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be written as well as read. Logarithmic space is sufficient to hold a constant number of <a href="/facts/Pointer_(computer_programming)/fPoNzy9b">pointers</a> into the input and a logarithmic number of Boolean flags, and many basic logspace algorithms use the memory in this way.
</p>

L (complexity) open-in-new

L (complexity)