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:
“Currently, U.S. society has been encouraged by its political and subsidized mass-media intelligentsia to view U.S. life as a continual “morning in America” paradise, where the only social problems occur in the inner cities. Psychologists call this denial.”
—Ishmael Reed (b. 1938)