| L (complexity) |
Article Index for L |
Information AboutL (complexity) |
|
A generalization of L is '''NL''' , which is the class of languages decidable in Logarithm ic space on a Nondeterministic Turing Machine . We then trivially have . Also, a decider using O(log ''n'') space cannot use more than 2O(log ''n'')=''n''O(1) time, because this is the total number of possible configurations; thus, , where ''' P ''' is the class of problems solvable in deterministic polynomial time. Every problem in L is complete under Log-space Reduction s; since this is useless, weaker reductions are defined which allow identification of stronger complete problems in L, but there is no generally accepted definition of L-complete. Important Open Problem s include whether L = '''P''', and whether L = '''NL'''. The related class of Function Problem s is FL . FL is often used to define Logspace Reduction s. A breakthrough October 2004 paper 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. REFERENCES
|
|
|