L (complexity)
id:
l-complexity-293-937091
title:
L (complexity)
text:
In computational complexity theory, L is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. 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 read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags
brand slug:
wiki
category slug:
encyclopedia
description:
Complexity class (logarithmic space)
original url:
https://en.wikipedia.org/wiki/L_(complexity)
date created:
date modified:
2023-12-12T23:19:01Z
main entity:
{"identifier":"Q1192782","url":"https://www.wikidata.org/entity/Q1192782"}
image:
fields total:
13
integrity:
14