Сложность вычислений

Circuit Complexity

Процессор - это булева схема. Каждый такт - новый слой вентилей. Вопрос: какие задачи принципиально требуют последовательных шагов, и какие можно «распараллелить до нуля»? Circuit Complexity даёт язык для этих вопросов - и первые доказанные ответы.

**GPU-вычисления:** матричное умножение в NC^2 - именно поэтому GPU с тысячами ядер даёт 100x ускорение на нейросетях
**Аппаратная верификация:** схемная сложность используется для доказательства нижних границ в дизайне чипов
**Криптография:** доказательство PARITY ∉ AC^0 - метод случайных ограничений - стало основой для атак на псевдослучайные генераторы

Boolean Circuits и размер

Процессор внутри - это сеть логических вентилей. Каждый вентиль принимает 1-2 бита, применяет AND/OR/NOT, отдаёт 1 бит. **Булева схема (Boolean circuit)** - именно такая сеть: ориентированный ациклический граф, где листья - входные биты, внутренние узлы - вентили, один выход - результат вычисления.

Ключевое отличие схем от машин Тьюринга: схема **фиксированного размера** работает только на входах фиксированной длины n. Для каждого n нужна своя схема C_n. Семейство {C_n} задаёт язык: x ∈ L тогда и только тогда, когда C_{|x|}(x) = 1.

**Размер (size)** схемы - аналог времени машины Тьюринга. **Глубина (depth)** - аналог параллельного времени: шаги, которые нельзя распараллелить.

Схема глубины d работает на входе длины n. Что означает глубина d в физическом смысле?

NC: параллельные вычисления

1979 год. Ник Пиппенгер задал вопрос: какие задачи можно решить **быстро параллельно**? Не просто «есть алгоритм», а «можно залить миллионом процессоров и получить ответ почти мгновенно». Так родился класс **NC** (Nick's Class).

Задача лежит в NC^k, если для неё существует семейство схем полиномиального размера size(n) = poly(n) и глубины depth(n) = O(log^k n). Глубина logарифмическая - это значит даже при n = миллиард, цепочка зависимостей содержит лишь ~30^k последовательных шагов.

**NC vs P:** NC ⊆ P, но неизвестно, NC = P или NC ⊊ P. Если NC ≠ P, то P-complete задачи принципиально «последовательные» - никакой параллелизм им не поможет.

Умножение n×n матриц лежит в NC^2. Что это означает на практике?

AC-иерархия

NC использует вентили с двумя входами (fan-in 2). Что если разрешить вентили с **неограниченным** количеством входов? Один OR-вентиль сразу над всеми входами - это мощнее. Так появляется класс **AC**: схемы с неограниченным fan-in и полиномиальным размером.

AC^k - семейство схем полиномиального размера и глубины O(log^k n), но вентили AND/OR принимают произвольно много входов. AC^0 - глубина O(1), то есть константная! Всего несколько слоёв вентилей, как бы ни рос вход.

**Razborov-Smolensky (1987):** MAJORITY ∉ AC^0 - тоже доказано! Нельзя посчитать большинство голосов схемой константной глубины, сколько бы широких вентилей не использовалось.

Почему результат 'PARITY ∉ AC^0' считается прорывом в теории сложности?

P/poly и advice

Семейство схем {C_n} может быть **несчислимым**: нет алгоритма, строящего C_n по n. Это открывает класс **P/poly** - задачи, решаемые полиномиальными схемами без ограничений на их вычислимость. Формально: машина Тьюринга с дополнительной подсказкой (advice) длины poly(n) для каждого n.

Advice a_n - строка длины poly(n), зависящая только от длины входа n, но не от самого входа. Машина M с advice решает язык L, если для каждого n существует a_n такое, что M(x, a_n) = 1 ⟺ x ∈ L для всех |x| = n.

**Почему P/poly не 'решает' NP:** advice нужно заранее знать - это как список ответов для конкретной длины входа. В реальности advice нельзя вычислить, если задача NP-трудна.

Чем P/poly отличается от P?