Изменения

Определим <tex>R_i</tex>&nbsp;=&nbsp; {''<tex>v''</tex>: существует путь из ''<tex>s'' </tex> в ''<tex>v'' </tex> длиной ≤ ''<tex>\le i''</tex>}. Другими словами это множество всех вершин,достижимых из ''<tex>s'' </tex> не более чем за ''<tex>i'' </tex> шагов. Обозначим |''R<subtex>i|R_i|</subtex>''| за ''r<subtex>ir_i</subtex>''.Заметим, что если <tex>t \notin R_{n-1}</tex>, где ''<tex>n''</tex> &nbsp;=&nbsp;<tex>|''V''|</tex>, то не существует путь ''<tex>s'' </tex> в ''<tex>t'' </tex> в графе ''<tex>G''</tex>, то есть <mathtex>\langle <G,s,t> \in \rangletext{STNONCON}</mathtex> ∈ STNONCON.

'''Лемма''': Можно построить алгоритм, который по данному ''r<subtex>ir_i</subtex>'' будет перечислять все вершины из ''R<subtex>iR_i</subtex>'' и удачно завершаться на логарифмической памяти. Если ''r<subtex>ir_i</subtex>'' больше истинного размера ''R<subtex>iR_i</subtex>'',то алгоритм завершится неудачно; однако если ''r<subtex>ir_i</subtex>'' меньше истинного размера ''R<subtex>iR_i</subtex>'', то алгоритм завершится удачно, но перечислит лишь некое подмножество ''R<subtex>iR_i</subtex>''.

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

Теперь имея Enum, можно индуктивно находить ''r<subtex>ir_i</subtex>''. Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину ''<tex>s''</tex>. Пусть известно значение ''r<subtex>ir_i</subtex>''. Напишем программу, которая на логарифмической памяти будет находить ''r<subtex>r_{i + 1}</subtex>''.

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

Теперь можно написать алгоритм, который будет недетерминировано решать задачу ''<tex>STNONCON'' </tex> на логарифмической памяти. Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>. Вычисление <tex>r_{n-1}</tex> происходит путем вызова Next <tex>n - 1</tex>, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.

<tex>r_n </tex> := 1 //''<tex>r_0</tex>''

<tex>r_n </tex> := Next(s, i, <tex>r_n</tex>, G) Enum(s, n - 1, <tex>r_n</tex>, G) //''Перечисляем вершины из <tex>R_{n - 1}</tex>''

Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения ''<tex>r_n'' </tex> и ''<tex>i'' </tex> необходимо <tex>2\log |G|</tex>, а для вызываемых Next и Enum необходимо <tex>O(\log |G|)</tex> памяти.