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 ¬ {\displaystyle \neg } indicates not, might be: