NL-complete Problems
Several problems are known to be NL-complete under log-space reductions, including ST-connectivity and 2-satisfiability. ST-connectivity asks for nodes S and T in a directed graph whether T is reachable from S. 2-satisfiability asks, given a formula of which each clause is the disjunction of two literals, if there is a variable assignment that makes the formula true. An example instance, where indicates not, might be:
Read more about this topic: NL (complexity)
Famous quotes containing the word problems:
“...I have wanted to believe people could make their dreams come true ... that problems could be solved. However, this is a national illness. As Americans, we believe all problems can be solved, that all questions have answers.”
—Kristin Hunter (b. 1931)