Editing L (complexity) (section)

==Complete problems and logical characterization==
Every non-trivial problem in '''L''' is [[Complete (complexity)|complete]] under [[log-space reduction]]s,<ref>See {{harvp|Garey|Johnson|1979|loc=Theorem 7.13 (claim 2)|p=179}}</ref> so weaker reductions are required to identify meaningful notions of '''L'''-completeness, the most common being [[FO (complexity)|first-order]] [[First-order reduction|reductions]].

A 2004 result by [[Omer Reingold]] shows that [[USTCON]], the problem of whether there exists a path between two vertices in a given [[undirected graph]], is in '''L''', showing that '''L''' = '''[[SL (complexity)|SL]]''', since USTCON is '''SL'''-complete.<ref>{{cite conference
 | last = Reingold | first = Omer
 | title = Undirected ST-connectivity in log-space
 | doi = 10.1145/1060590.1060647
 | id = {{ECCC|2004|04|094}}
 | mr = 2181639
 | pages = 376–385
 | publisher = ACM, New York
 | conference = [[Symposium on Theory of Computing|STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing]]
 | url = http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps
 | year = 2005}}</ref>

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 theory|graph theoretical]] terms, this turns every [[connected component (graph theory)|connected component]] into a [[clique (graph theory)|clique]]). This result has application to database [[query language]]s: ''[[data complexity]]'' of a query is defined as the complexity of answering a fixed query considering the data size as the variable input. For this measure, queries against [[relational database]]s with complete information (having no notion of [[Null (SQL)|null]]s) as expressed for instance in [[relational algebra]] are in '''L'''.