Examples
One important NL-complete problem is ST-connectivity (or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.
Another important NL-complete problem is 2-satisfiability (Papadimitriou 1994 Thrm. 16.3), the problem of determining whether a boolean formula in conjunctive normal form with two variables per clause is satisfiable.
The problem of unique decipherability of a given variable-length code was shown to be co-NL-complete by Rytter (1986); Rytter used a variant of the Sardinas–Patterson algorithm to show that the complementary problem, finding a string that has multiple ambiguous decodings, belongs to NL. Because of the Immerman–Szelepcsényi theorem, it follows that unique decipherability is also NL-complete.
Read more about this topic: NL-complete
Famous quotes containing the word examples:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)