Изменения

Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</tex>, придумаем недетерминированый недетерминированный алгоритм, использующий <tex>O(\log |G|)</tex> дополнительной памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.

 Можно построить недетерминированный алгоритм, который будет допускать решать задачу <tex>r_i</tex> (то есть определять, существует ли путь из <tex>s</tex> в <tex>t</tex> такой длины) и при этом будет перечислять все вершины из <tex>R_i\mathrm{NCONN}</tex> на <tex>O(\log |G|)</tex> памяти (это будет доказано ниже).

| statement = Можно построить недетерминированный алгоритм, который будет допускать решать задачу <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i\mathrm{NCONN}</tex> на <tex>O(\log |G|)</tex> памяти.

Можно Для начала приведем недетерминированный алгоритм, находящий путь между двумя вершинами с длиной не более заданной. '''CheckPath'''(<tex>s,t,k</tex>) <tex>cur \leftarrow s</tex> '''for''' <tex>i = 1..k</tex> '''do''' <tex>v \leftarrow_? \left\{1..n\right\}</tex> '''if''' <tex>(cur,v) \notin E</tex> '''reject''' <tex>cur \leftarrow v</tex> '''if''' <tex>cur \ne t</tex> '''reject''' Теперь можно построить недетерминированный алгоритм, который будет допускать принимать на вход <tex>r_i</tex> и при этом (в случае корректности <tex>r_i</tex>) будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти. '''EnumEnumerate'''(<tex>s, i, r_i, G</tex>) <tex>counter</tex> <tex>\leftarrow0 </tex> 0 //количество уже найденных и выведенных элементов

'''continue''' or find path <tex>tryV \leftarrow_? \left\{0, 1\right\}</tex> //недетерминированно угадываем путь из s до v или переходим к следующей вершине '''if''' <tex>tryV = 0</tex> '''continue''' '''CheckPath'''<tex>(s,v,i)</tex>

'''returnoutput''' <tex>v</tex> //выдаем вершину, до которой угадали путь '''if''' (<tex>counter \geq neq r_i</tex>) //не нашли <tex>r_i</tex> вершин, не допускаем, завершаем работу '''accept''' '''reject''' //не нашли <tex>r_i</tex> вершин, не допускаем

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

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

Теперь, имея '''EnumEnumerate''', можно по индукции находить строить <tex>r_i</tex>.

<tex>r = \leftarrow 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \in R_{i+1}</tex> '''for''' <tex>v = 1..n</tex>; : <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex> '''for''' <tex>u \in V : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex> '''if''' (<tex>u</tex> '''in''' '''EnumEnumerate'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex>

Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''EnumEnumerate'''.

<tex>r_n = \leftarrow 1</tex> //<tex>r_0 = 1</tex> '''for''' <tex>i = 0..n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex>

'''if''' (<tex>t1t</tex> '''in''' '''EnumEnumerate'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept'''

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