Изменения

Решим задачу STNONCON на логарифмической памятии покажем, что STNONCON ∈ NL.

Enum перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из ''s''. Для угадывания пути достаточно логарифмической <tex>O(\log |G|)</tex> памяти, так как необходимо помнить лишь текущую вершину пути и пытаться угадывать следующую. Enum является недетерминированой программой и если существует порядок исполнения, чтобы достичь ACCEPT, то он достигается.

Данный алгоритм изначально учитывает ''s'', а затем перебирает всех возможных кандидатов на попадание в <tex>R_{i + 1}</tex>. Для каждого из них перебираются все ребра, в него входящие. Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>. Алгоритм использует логарифмическую память<tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь ''v'', ''u'', ''r'' и еще поочередно значения полученные в результате вызова Enum.

Теперь можно написать алгоритм, который будет недетерминировано решать задачу ''STNONCON'' на логарифмической памяти. Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершиниз <tex>R_{n - 1}</tex>. Вычисление <tex>r_{n-1}</tex> происходит путем вызова Next <tex>n - 1</tex>, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение. <code>NONCON(G, s, t) r_n := 1 //''<tex>r_0</tex>'' '''for''' i = 0..n-2 '''do''' //''Вычисляем <tex>r_{n - 1}</tex>'' r_n := Next(s, i, r_n, G) Enum(s, n - 1, r_n, G) //''Перечисляем вершины из <tex>R_{n - 1}</tex>'' '''if''' t in output '''then''' //''Если t была перечислена то t достижима и выдаем REJECT, иначе ACCEPT'' REJECT '''else''' ACCEPT </code> Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения ''r_n'' и ''i'' необходимо <tex>2\log |G|</tex>, а для вызываемых Next и Enum необходимо <tex>O(\log |G|)</tex> памяти. Таким образом показано, что STNONCON ∈ NL.