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:
“One of the annoying things about believing in free will and individual responsibility is the difficulty of finding somebody to blame your problems on. And when you do find somebody, it’s remarkable how often his picture turns up on your driver’s license.”
—P.J. (Patrick Jake)