NL = coNL: как счёт заменяет список достижимых вершин

Если понимаешь роль точного счётчика - переходи к «Теперь сам».

Как думаешь: как подтвердить отсутствие пути без обхода?

В графе сто тысяч вершин. На рабочей ленте помещаются несколько номеров, но не сто тысяч отметок посещения. Для ответа «достижима» можно угадывать очередное ребро, проверяя его чтением входа. Один удачный путь будет принимающей ветвью. А что предъявить для ответа «недостижима»? Простое «не нашёл» не подходит: другая ветвь могла найти путь.

В NL принимается вход, для которого существует хотя бы одна принимающая ветвь. Значит, ошибочная догадка об отсутствии пути не должна иметь ни одной возможности закончиться принятием. В доказательстве каждую недосчитанную вершину ловит известная точная численность предыдущего слоя.

На что это похоже

Представь проверку списка гостей без возможности переписать его целиком. Если организатор достоверно сказал, что пришло ровно 17 человек, достаточно по одному проверить 17 разных гостей, чтобы исключить присутствие любого другого. Если число 17 просто угадано, такой вывод недействителен. Поэтому сначала надо научиться получать достоверное число, начиная с маленького случая, где ответ известен заранее.

Механизм: растим число, не сохраняя множество

Обозначим Aᵢ множество вершин, достижимых из s не более чем за i рёбер, а cᵢ - его размер. Начало: A₀ = {s}, значит c₀ = 1. Если в графе n вершин, любой существующий путь можно укоротить до простого длины не больше n − 1. Поэтому после n − 1 слоёв множество перестаёт нуждаться в расширении.

Пусть точное cᵢ уже получено. Для каждой вершины v надо решить, входит ли она в следующий слой. Перебираем все вершины u в фиксированном порядке. Недетерминированно выбираем, считать ли u членом Aᵢ. Положительный выбор подтверждаем угаданным путём длины не больше i; если путь неверен, ветвь отвергается. Считаем число подтверждений. Если оно не равно cᵢ, ветвь тоже отвергается. Разные номера u перебираются по одному разу, поэтому нельзя добрать счётчик повтором одной вершины.

Когда подтверждено ровно cᵢ вершин, перечислено всё Aᵢ. Можно достоверно определить, есть ли у v предшественник в Aᵢ; вершину s включаем отдельно. Так последовательно считаем cᵢ₊₁, не записывая само множество. Повторный перебор входа экономит память ценой времени.

Почему счётчик достоверен? По индукции неверные положительные утверждения не проходят проверку путём, а пропуск настоящей вершины даёт слишком маленький счётчик. При верном cᵢ существует ветвь, которая угадает все нужные вершины и пути. Любая выжившая ветвь получит правильное cᵢ₊₁. Это утверждение о всех ветвях, а не обещание удачного случайного запуска.

Наконец, зная полное число достижимых вершин, перечисляем их с проверкой, запрещая цель t. Если удалось подтвердить точное число без t, пути нет. В памяти лежит постоянное число индексов и счётчиков до n; каждый занимает O(log n) бит. Угаданный путь не хранится целиком: только текущая вершина и остаток длины.

Правило

Недетерминированность позволяет подтверждать положительные догадки. Точное число объектов позволяет превратить полное перечисление подтверждений в доказательство отсутствия остальных. Равенство NL и coNL доказано для пространства; переносить его на NP и coNP нельзя.

Разбор: четыре слоя на маленьком графе

Программа ниже намеренно хранит множества. Это наглядная проверка чисел, а не реализация логарифмической памяти. Она показывает значения, которые машина доказательства получает повторными чтениями и угадыванием путей.

from itertools import combinations


def sloi(n, rebra, start):
    a = {start}
    otvet = [a.copy()]
    for _ in range(n - 1):
        a |= {v for u, v in rebra if u in a}
        otvet.append(a.copy())
    return otvet


def est_put(n, rebra, start, finish, limit):
    if start == finish:
        return True
    if limit == 0:
        return False
    return any(est_put(n, rebra, v, finish, limit - 1)
               for u, v in rebra if u == start)


def proverit_spisok(n, rebra, start, limit, chislo, spisok):
    if len(set(spisok)) != len(spisok):
        return False
    if len(spisok) != chislo:
        return False
    return all(est_put(n, rebra, start, v, limit)
               for v in spisok)


n = 6
rebra = [(0, 1), (1, 2), (2, 1), (2, 3), (4, 5)]
a = sloi(n, rebra, 0)
for i, s in enumerate(a[:4]):
    print('слой', i, 'число', len(s), 'вершины', sorted(s))
print('пропущена вершина:',
      proverit_spisok(n, rebra, 0, 3, 4, [0, 1, 2]))
print('дописана чужая:',
      proverit_spisok(n, rebra, 0, 3, 4, [0, 1, 2, 4]))
print('правильный список:',
      proverit_spisok(n, rebra, 0, 3, 4, [0, 1, 2, 3]))

слой 0 число 1 вершины [0]
слой 1 число 2 вершины [0, 1]
слой 2 число 3 вершины [0, 1, 2]
слой 3 число 4 вершины [0, 1, 2, 3]
пропущена вершина: False
дописана чужая: False
правильный список: True

Список из трёх вершин не подтверждает отсутствие четвёртой, потому что известный счётчик равен четырём. Добавить вершину 4 вместо пропущенной 3 тоже нельзя: до неё нет пути. В машине из доказательства список передаётся проверке по одной записи, а не целиком, как в этой демонстрации.

Разбор: что будет с неверным числом

Если вместо четырёх объявить c = 3, список 0,1,2 пройдёт проверки путей и длины. Тогда программа ошибочно «докажет» отсутствие пути до 3. Именно поэтому входной счётчик нельзя угадывать без обоснования. Индукция начинается с достоверной единицы и на каждом шаге опирается на уже достоверное число. Отрицание получается из полноты перечисления, а не из неудачного поиска.

Что ломается без этого

Замена «существует принимающая ветвь» на «обычно удалось угадать» подменяет NL вероятностным классом. Хранение битового списка достижимости подменяет логарифмическую память линейной. Замена точного числа на верхнюю оценку тоже неверна: верхняя оценка не сообщает, сколько положительных свидетелей ещё не найдено.

Зачем это в работе

Теорема помогает читать классификации задач проверки программ и графов: отрицательная постановка в малой памяти не обязательно труднее положительной. Сам индуктивный алгоритм редко заменяет обычный обход в прикладной программе; его задача - доказать границу ресурса. Отдельный полезный приём шире: счётчик удостоверенных объектов может заменить их явный список, если полнота счётчика доказана независимо.

Теперь сам

В графе шесть вершин, из s достижимы ровно четыре. Цель не предъявлена, но предъявлены три других достижимых вершины с верными путями. Можно ли заключить, что цель недостижима?