L (complexity class)

from Wikipedia, the free encyclopedia

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:

LNLNCPNPPSPACE

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

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

  1. ^ 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 .
  2. 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 .
  3. ^ 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 .

Web links

  • L . In: Complexity Zoo. (English)
  • SL . In: Complexity Zoo. (English)