If a deterministic algorithm exists for solving any one of the NL-complete problems in logarithmic memory space, then NL = L. NL consists of the decision problems that can be solved by a nondeterministic Turing machine with a read-only input tape and a separate read-write tape whose size is limited to be proportional to the logarithm of the input length.
Similarly, L consists of the languages that can be solved by a deterministic Turing machine with the same assumptions about tape length.
Because there are only a polynomial number of distinct configurations of these machines, both L and NL are subsets of the class P of deterministic polynomial-time decision problems.
16.3), the problem of determining whether a boolean formula in conjunctive normal form with two variables per clause is satisfiable.
Additional NL-complete problems on propositional logic, algebra, linear system, graph, finite automata, context-free grammar are listed in Jones (1976).