L (complexity class)
In complexity theory , L denotes the class of decision problems that can be solved by a deterministic Turing machine with logarithmic space consumption . In order to be able to define logarithmic space consumption, it must be assumed that the input for the decision problem is given on a separate input band . This can only be read and is not taken into account when specifying the space required.
Relationship to other complexity classes
The following relationships are known:
According to the place hierarchy record , at least one of these inclusions must be real, since L is a real subset of PSPACE. So far, however, it is unknown which this is and whether, for example, L = NL or L = P applies.
SL
The class SL ( English for symmetric log-space ) was originally defined using the concept of the symmetric Turing machine . An alternative - and more frequently used - characterization, on the other hand, defines SL as the class of all problems that can be reduced to the USTCON problem by LOGSPACE reduction . This class is between L and NL, so it applies
- L ⊆ SL ⊆ NL.
In 2004 , however, Omer Reingold showed that USTCON can also be solved with logarithmic space requirements. The equality L = SL thus applies.
Known issues in L
- Accessibility problem in undirected graphs
- Planarity of graphs, i.e. H. to decide whether a given graph is planar.
A variety of problems in the L class are listed in the article by Cook and McKenzie and the Compendium by Alvarez and Greenlaw.
literature
- Omer pure gold. Undirected ST connectivity in log space . Electronic Colloquium on Computational Complexity. No. 94, 2004.
- Stephen A. Cook, Pierre McKenzie: Problems complete for deterministic logarithmic space . In: Journal of Algorithms . tape 8 , no. 3 , 1987, pp. 385-394 , doi : 10.1016 / 0196-6774 (87) 90018-6 .
- C. Alvarez, R. Greenlaw: A compendium of problems complete for symmetric logarithmic space . In: computational complexity . tape 9 , no. 2 , 2000, pp. 123-145 , doi : 10.1007 / PL00001603 .
Individual evidence
- ^ Eric Allender, Meena Mahajan: The Complexity of Planarity Testing . In: H. Reichel, S. Tison (Ed.): STACS 2000 (= Lecture Notes in Computer Science . Volume 1770 ). Springer, Berlin, Heidelberg 2000, ISBN 978-3-540-67141-1 , pp. 87-98 , doi : 10.1007 / 3-540-46541-3_7 .
- ↑ Stephen A. Cook, Pierre McKenzie: Problems complete for deterministic logarithmic space . In: Journal of Algorithms . tape 8 , no. 3 , 1987, pp. 385-394 , doi : 10.1016 / 0196-6774 (87) 90018-6 .
- ^ C. Alvarez, R. Greenlaw: A compendium of problems complete for symmetric logarithmic space . In: computational complexity . tape 9 , no. 2 , 2000, pp. 123-145 , doi : 10.1007 / PL00001603 .