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

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

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

Утверждение

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

Доказательство

Для доказательства NL-полноты необходимо показать, что эта задача NL-трудная и принадлежит классу NL.