Изменения

'''Лемма''': Можно построить недетерминированный алгоритм, который будет принимать верно заданное <tex>r_i</tex> (AAAA) и при этом будет перечислять все вершины из <tex>R_i</tex> на логарифмической памяти.

counter := 0 //''количество уже найденных и выведенных элементов'' '''for''' v = 1..n '''do''' //''перебираем все вершины графа'' '''continue''' or ''find path'' //''недетерминировано выбираем переходить к следующей вершине или угадываем путь до данной''

'''yield return''' v //''выдаем вершину, до которой угадали путь'' '''if''' counter <tex>\ge r_i</tex> '''then''' //''нашли <tex>r_i</tex> вершин, принимаем и завершаем работу''

<texcode>\text{Enum}</texcode> перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.

<tex>\text{Enum}</tex> является недетерминированым алгоритмом , и если существует порядок его исполнения, чтобы достичь достигающий <tex>\text{ACCEPT}</tex>, то он достигаетсяпроисходит допуск.

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

r := 1 //''<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \in R_{i + 1}</tex>''(∈AAAAAAAA) '''for''' v = 1..n; <tex>v \neq s</tex> '''do''' //''перебираем все вершины графа, кроме s -- это кандидаты на попадание в <tex>R_{i + 1}</tex>''