NL-complete

Among the problems in NL, some are the hardest of the bunch: solve one of those and you have effectively cracked the whole class. A problem is NL-complete when it is both in NL and is a kind of universal NL problem, one that every other NL problem can be translated into. It is the NL analogue of NP-completeness, with the same logic: these complete problems capture the full difficulty of their class, so a faster algorithm for any single one would speed up all of NL at once.

To make this precise we need a notion of translation gentle enough not to cheat. For NL the right tool is the log-space reduction: a problem B is NL-hard if every language A in NL log-space-reduces to B, and B is NL-complete if it is also itself in NL. We must use log-space (not polynomial-time) reductions here, because a polynomial-time reduction could itself be more powerful than NL and would blur the very distinctions we are trying to draw. The undisputed flagship is directed graph reachability (the PATH problem: is there a directed path from s to t?). It is in NL, and every NL computation can be encoded as a reachability question in its configuration graph, so PATH is NL-complete.

NL-completeness is the lever for the whole class. Because PATH is NL-complete and NL equals co-NL (Immerman-Szelepcsenyi), the complement of reachability is NL-complete too. And since NL is contained in P, every NL-complete problem has a polynomial-time algorithm; the open question is whether it has a deterministic log-space one, which is exactly the L versus NL question. Caveat: NL-hard and NL-complete differ, just as with NP. A problem can be NL-hard while living outside NL (being even harder), and only the ones that are also in NL earn the label complete.