NL-полнота задачи о достижимости в графе

Формулировка задачи

Даны ориентированный граф [math] G = \langle V, E \rangle [/math] и две вершины [math] s, t[/math] в нем. Необходимо проверить, правда ли, что в графе [math] G [/math] существует путь из вершины [math] s [/math] в вершину [math] t [/math]. Эту задачу принято называть [math] REACH [/math].

Утверждение

Задача [math] REACH [/math] NL-полна.