L и NL: логарифмическое пространство

1987 год. Иммерман доказывает NL = co-NL. Тот же год - Селепченьи независимо. Шок: обычно доказать что класс замкнут относительно дополнения - крайне трудно. Для NP это открытый вопрос. NL оказался исключением. Параллельно - другой факт: L использует $O(\log n)$ памяти. При n = 1 миллиард: $\log_2(10^9) \approx 30$ бит = 4 байта. Весь рабочий стек алгоритма. Это не теория - STCON для неориентированных графов (Reingold, 2005) решается детерминированно в O(log n). А ещё парадокс: graph reachability в ориентированных графах NL-complete. В неориентированных - L. Один тип рёбер меняет сложностной класс.

• **Graph reachability в социальных сетях:** 6 degrees of separation как STCON instance - каждый запрос "есть ли путь между A и B в графе из 3 миллиардов вершин" это NL задача
• **2-SAT solver в constraint propagation:** linear time через SCC + logspace via NL, используется в SAT preprocessors, dependency resolution (apt, npm), circuit verification
• **Streaming algorithms:** HyperLogLog считает количество уникальных элементов в $O(\log \log n)$ бит - практический аналог L-алгоритмов для потоковой обработки
• **Database query evaluation:** logspace-сведения показывают что SQL (первый порядок) ⊆ PSPACE, а многие запросы решаются в NL - это объясняет почему оптимизатор может работать с ограниченной памятью

STCON: достижимость как центральная задача NL

**L** (logspace) - класс задач, решаемых детерминированной машиной Тьюринга с $O(\log n)$ рабочей памяти. Входная лента только для чтения, выходная - только для записи. Рабочая лента - единственное что считается. При $n = 10^9$: $\log_2(10^9) \approx 30$ бит - 4 байта рабочей памяти на весь алгоритм. **STCON** (s-t connectivity) - задача достижимости: дан ориентированный граф $G$ и вершины $s$, $t$, существует ли путь из $s$ в $t$? Наивный DFS использует $O(n)$ памяти для стека вызовов - это P, не L. Но STCON лежит в NL: недетерминированная машина угадывает следующую вершину пути по одному шагу, храня только текущую вершину - $O(\log n)$ бит.

**Теорема Рейнгольда (2005):** USTCON (undirected s-t connectivity) принадлежит L. Доказательство использует явную конструкцию expander-графов через zigzag product. Это один из крупнейших результатов теории сложности 2000-х. До 2005 года было известно только что USTCON in SL (симметричный logspace) - Рейнгольд доказал SL = L. Следствие: неориентированная достижимость решается детерминированно в 4 байтах рабочей памяти.

**Почему ориентированность важна:** в неориентированном графе случайное блуждание гарантированно покрывает весь граф за $O(n^3)$ шагов (cover time). Это позволяет сделать derandomization через explicit expander. В ориентированном графе случайное блуждание может зациклиться - cover time не гарантирован. Именно поэтому STCON (directed) - NL-complete, а USTCON (undirected) - L.

NL-полнота и logspace-сведения

NL-полнота определяется через **logspace-сведения** - строго слабее чем полиномиальные. Это важно: полиномиальное сведение могло бы само решить задачу за полиномиальное время, что сделало бы понятие NL-полноты тривиальным. Logspace-сведение $A \leq_L B$: существует функция $f$, вычислимая в $O(\log n)$ пространстве, такая что $x \in A \iff f(x) \in B$. **STCON - NL-complete:** любая задача в NL logspace-сводится к STCON. Идея: конфигурации недетерминированной TM на входе $x$ образуют граф - вершины конфигурации, рёбра - переходы. Входное слово $x$ принимается тогда и только тогда, когда из начальной конфигурации достижима принимающая. Этот граф вычислим в logspace.

**Почему logspace-сведения, а не poly-time?** Если использовать полиномиальные сведения, то NP-полные задачи автоматически были бы NL-полными (через poly-time сведение из любой задачи в NP). Logspace-сведения сохраняют "мощность" класса: если $A \leq_L B$ и $B \in$ L, то $A \in$ L. Это делает понятие полноты содержательным - NL-полные задачи действительно наиболее сложные в NL.

Теорема Иммермана-Селепченьи: NL = co-NL

**1987 год.** Иммерман и Селепченьи независимо доказывают: **NL = co-NL**. Шок в сообществе. co-NL - это класс задач, дополнения которых в NL. co-STCON: дан граф, НЕ существует пути из $s$ в $t$? Для NP vs co-NP считается что NP $\neq$ co-NP (иначе NP замкнут по дополнению, что противоречит интуиции). Для NL это оказалось неверным. Ключевая идея: **индуктивный подсчёт**. Нельзя напрямую угадать, что пути нет. Но можно посчитать количество вершин, достижимых из $s$ за $k$ шагов - используя $O(\log n)$ пространства. Если итоговое количество достижимых вершин не включает $t$ - пути нет.

**Почему это нетривиально:** для NP vs co-NP мы не умеем аналогичного. Сертификат НЕ-выполнимости формулы SAT - это доказательство что для ВСЕХ присвоений формула ложна. Краткого сертификата нет (предположительно). Для NL работает потому что logspace-машина может инкрементально подсчитывать достижимость, не храня весь граф. Пространство можно переиспользовать на каждом шаге индукции.

**Следствие для STCON:** co-STCON ("пути нет") тоже NL-complete. Значит STCON и co-STCON одинаково сложны - обе NL-complete. Это аналог того, что SAT и co-SAT были бы NP-complete одновременно (чего мы не знаем для NP).

Теорема о пространственной иерархии

**Теорема о пространственной иерархии:** для функций $s_1(n) = o(s_2(n))$ где $s_2$ space-constructible, выполняется SPACE$(s_1) \subsetneq$ SPACE$(s_2)$. Следствие: L $\neq$ PSPACE - классы строго различны. Доказательство через диагонализацию: конструируется машина, которая при пространстве $s_2(n)$ решает задачу, не решаемую ни одной машиной с пространством $s_1(n)$. Аналог теоремы об иерархии времени, но для пространства. Известные факты: L $\subsetneq$ PSPACE (доказано), L $\subseteq$ NL $\subseteq$ P $\subseteq$ NP $\subseteq$ PSPACE (все включения). Открытые вопросы: L vs NL, NL vs P, P vs NP - все независимы друг от друга.

**L $\neq$ NL или нет?** Если L = NL, то недетерминизм не помогает при логарифмическом пространстве. Если L $\neq$ NL, то существуют задачи (например STCON в ориентированных графах), которые принципиально требуют недетерминизма. Это независимо от P vs NP - можно было бы иметь L = NL и P $\neq$ NP, или L $\neq$ NL и P = NP. Все три разделения - самостоятельные открытые вопросы.

Ключевые идеи

• **L и NL:** L = детерминированный O(log n) пространство, NL = недетерминированный. STCON (directed) - NL-complete. USTCON (undirected) - L (Reingold 2005)
• **NL-полнота через logspace-сведения:** STCON - каноническая NL-complete задача. 2-SAT in NL через SCC. Logspace-сведения слабее poly-time - это содержательное понятие полноты
• **NL = co-NL (Иммерман-Селепченьи 1987):** индуктивный подсчёт достижимых вершин в O(log n). Следствие: co-STCON тоже NL-complete. Аналог для NP (NP = co-NP) - открытый вопрос
• **Space Hierarchy и открытые вопросы:** L $\subsetneq$ PSPACE доказано. L vs NL, NL vs P - независимые открытые вопросы, не связанные с P vs NP

Связанные темы

Как L и NL вписываются в теорию сложности и практику:

• PSPACE и PSPACE-полнота — L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE - иерархия классов. Space Hierarchy отделяет L от PSPACE строго.
• Big-O и анализ сложности — O(log n) пространство - базовое определение L. Анализ алгоритмов по памяти, не только по времени.
• Вычислимость и неразрешимость — Space Hierarchy Theorem использует диагонализацию - тот же метод что в теореме Тьюринга о неразрешимости Halting Problem.
• Регулярные языки — Регулярные языки распознаются DFA - O(1) пространство. L - следующий уровень: O(log n). Параллель с иерархией Хомского.

Вопросы для размышления

• Reingold доказал USTCON ∈ L через explicit expander graph construction. Почему derandomization (замена случайного блуждания детерминированным) работает для неориентированных, но не для ориентированных графов?
• NL = co-NL, но предположительно NP ≠ co-NP. В чём принципиальная разница между logspace-сертификатом пути (NL) и poly-time сертификатом выполнимости (NP), которая объясняет асимметрию?
• Space Hierarchy Theorem: SPACE(log n) ⊊ SPACE(log² n). Savitch: NL ⊆ SPACE(log² n). Означает ли это что NL ⊊ PSPACE строго, или только что NL ⊆ SPACE(log² n) ⊆ PSPACE?

Связанные уроки

• cplx-04
• cplx-01
• alg-01-big-o
• comp-05
• fl-05-regex
• alg-02-space