L (complexity)

L (complexity)

In computational complexity theory, L (also known as LSPACE) is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags and many basic logspace algorithms use the memory in this way.

L is a subclass of NL, which is the class of languages decidable in logarithmic space on a nondeterministic Turing machine. Using the construction of Savitch's theorem, one can see that NL is contained in the complexity class P of problems solvable in deterministic polynomial time. Thus L ⊆ NL ⊆ P. The inclusion of L into P can also be proved more directly: a decider using O(log n) space cannot use more than 2O(log n) = nO(1) time, because this is the total number of possible configurations.

Every non-trivial problem in L is complete under log-space reductions so weaker reductions are required to identify meaningful notions of L-completeness. These include NC1-reductions and DLOGTIME-reductions.

Important open problems include whether L = P, and whether L = NL.

The related class of function problems is FL. FL is often used to define logspace reductions.

A breakthrough October 2004 paper[1] by Omer Reingold showed that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is in L, establishing that L = SL, since USTCON is SL-complete.

One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first-order logic with an added commutative transitive closure operator (in graph theoretical terms, this turns every connected component into a clique).

L is low for itself, because it can simulate log-space oracle queries (roughly speaking, "function calls which use log space") in log space, reusing the same space for each query.

Use outside of complexity world

The main idea of logspace is that you can mostly count things up to a polynomial number using logspace and remember pointers to position of the input.

The logspace class is therefore useful to model computation where the input is too big to fit in the RAM of a computer. Long DNA sequences and databases are good examples of problems where only a constant part of the input will be in RAM at a given time and where we have pointers to compute the next part of the input to inspect, thus using only logarithmic memory.

References

  1. ^ Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.

See also

  • L/poly, a nonuniform variant of L that captures the complexity of polynomial-size branching programs

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Complexity management — is a business methodology that deals with the analysis and optimization of complexity in enterprises. Effects of complexity pertain to all business processes along the value chain and hence complexity management requires a holistic approach.… …   Wikipedia

  • Complexity theory and organizations — Complexity theory and organizations, also called complexity strategy or complex adaptive organization, is the use of Complexity theory in the field of strategic management and organizational studies. Contents 1 Overview 2 Early research 3 Later… …   Wikipedia

  • compLexity — coL Логотип организации Страна …   Википедия

  • Complexity theory and strategy — Complexity theory has been used extensively in the field of strategic management and organizational studies, sometimes called complexity strategy or complex adaptive organization on the internet or in popular press. Broadly speaking, complexity… …   Wikipedia

  • Complexity (journal) —   Discipline Complex Systems …   Wikipedia

  • Complexity, Problem Solving, and Sustainable Societies — is a paper on energy economics by Joseph Tainter from 1996. Contents 1 Focus 1.1 Attempts 1.2 Requirement of knowledge 2 See …   Wikipedia

  • Complexity theory — may refer to: The study of a complex system or complex systems Complexity theory and organizations, the application of complexity theory to strategy Complexity economics, the application of complexity theory to economics Chaos theory, the study… …   Wikipedia

  • compLexity — Kürzel coL Manager Vereinigte Staaten Jason „1“ Lake …   Deutsch Wikipedia

  • Complexity — Com*plex i*ty, n.; pl. {Complexities}. [Cf. F. complexit[ e].] 1. The state of being complex; intricacy; entanglement. [1913 Webster] The objects of society are of the greatest possible complexity. Burke. [1913 Webster] 2. That which is complex;… …   The Collaborative International Dictionary of English

  • complexity — complexity. См. сложность генома. (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) …   Молекулярная биология и генетика. Толковый словарь.

  • complexity — index complication, confusion (turmoil), enigma, entanglement (confusion), imbroglio, impasse …   Law dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”