L (complexity)

In complexity theory, L denotes the class of decision problems that can be solved by a deterministic Turing machine with logarithmic space consumption. To be able to log space requirements define It must be assumed that the input for the decision problem on a separate input band is given. This is read-only and will not be considered for the specification of the space consumption.

Relation to other complexity classes

The following relations are known:

After the space hierarchy set at least one of these inclusions must be real, since L is a proper subset of PSPACE. So far, however, is unknown what this is, and whether, for example, L = NL or L = P holds.

SL

The SL class (English for symmetric log-space ) was originally defined on the concept of symmetric Turing machine. An alternative - and frequently used - Characterization defined, however SL as the class of all reducible by LOGSPACE - reduction to the problem USTCON problems. This class is between L and NL, it is therefore

In 2004, Omer Reingold showed, however, that can be solved with logarithmic space USTCON. Thus, the equality L = SL applies.

Known issues in L

  • Reachability problem in graphs
527331
de