Класс NC

Один из больших открытых вопросов теории сложности вычислений — является ли собственным каждое вложение NC-иерархии. Как было замечено Пападимитриу, если для какого-то ${\displaystyle i}$ верно NCⁱ = NCⁱ⁺¹, то NCⁱ = NC^j для всех ${\displaystyle j\geqslant i}$, и как следствие, NCⁱ = NC. Это наблюдение называется сворачиванием NC-иерархии, потому что даже из одного равенстве в цепи вложений:

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots }$

следует, что вся NC-иерархия «сворачивается» до какого-то уровня ${\displaystyle i}$. Таким образом, возможны два варианта:

1. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}}$
2. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}.}$

Широко распространено мнение, что верно именно (1), хотя пока не обнаружено никаких доказательств в отношении истинности того или иного утверждения.

Докажем, что ветвящаяся программа (ВП) с константной шириной и полиномиальным размером может быть превращена в схему из NC¹.

От противного: пусть есть схема C из NC¹. Без ограничения общности, будем считать что в ней используются только вентили И и НЕ.

Определение: ВП называется ${\displaystyle \sigma }$-вычисляющей булеву функцию ${\displaystyle f}$ или ${\displaystyle (\sigma -f)}$, если при ${\displaystyle f=0}$ она дает результат — тождественную перестановку, а при ${\displaystyle f=1}$ её результат — ${\displaystyle \sigma }$-перестановка. Так как наша схема C описывает какую-то булеву функцию ${\displaystyle f}$ и только её, можем взаимно заменять эти термины.

Для доказательства будем использовать две леммы:

Лемма 1: Если есть ВП, ${\displaystyle \sigma }$-вычисляющая ${\displaystyle f}$, то существует и ВП, ${\displaystyle \sigma ^{-1}}$-вычисляющая ${\displaystyle f}$ (то есть, равная ${\displaystyle id}$ при ${\displaystyle f=0}$, и равная ${\displaystyle \sigma ^{-1}}$ при ${\displaystyle f=1}$.

Доказательство: так как ${\displaystyle \sigma }$ и ${\displaystyle \sigma ^{-1}}$ — циклы, а любые два цикла являются сопряженными, то существует такая перестановка ${\displaystyle \pi }$, что ${\displaystyle \sigma ^{-1}}$ = ${\displaystyle \pi \sigma \pi ^{-1}}$. Тогда домножим на ${\displaystyle \pi }$ перестановки ${\displaystyle p_{1}}$ и ${\displaystyle q_{1}}$ из первой инструкции ВП слева (чтобы получить перестановки ${\displaystyle {\pi }p_{1}}$ и ${\displaystyle {\pi }q_{1}}$), а перестановки из последней инструкции домножим на ${\displaystyle \pi ^{-1}}$ справа (получим ${\displaystyle p_{n}\pi ^{-1}}$ и ${\displaystyle q_{n}\pi ^{-1}}$). Если до наших действий (без ограничения общности) ${\displaystyle {p_{1}}{p_{2}}...{p_{n}}}$ был равен ${\displaystyle id}$, то теперь результат будет ${\displaystyle {\pi }id{\pi }^{-1}=id}$, а если был равен ${\displaystyle \sigma }$, то результат равен ${\displaystyle \pi \sigma \pi ^{-1}=\sigma ^{-1}}$. Так, мы получили ВП, ${\displaystyle \sigma ^{-1}}$-вычисляющую ${\displaystyle f}$, с той же длиной (количество инструкций не поменялось).

Примечание: если домножить вывод ВП ${\displaystyle (\sigma ^{-1}-f)}$ на ${\displaystyle \sigma }$ справа, то очевидным образом получим ВП, ${\displaystyle \sigma }$-вычисляющую функцию ${\displaystyle {\neg }f}$.

Лемма 2: Если есть два ВП: ${\displaystyle \sigma }$-вычисляющая ${\displaystyle f}$ и ${\displaystyle \gamma }$-вычисляющая ${\displaystyle t}$ с длинами ${\displaystyle l_{1}}$ и ${\displaystyle l_{2}}$, где ${\displaystyle \sigma }$ и ${\displaystyle \gamma }$ — 5-цикличные перестановки, то существует ВП с 5-цикличной перестановкой ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}}$ такая, что ВП ${\displaystyle \varepsilon }$-вычисляет${\displaystyle f{\wedge }t}$, и её размер не превосходит ${\displaystyle 2(l_{1}}$ + ${\displaystyle l_{2})}$.

Доказательство: Выложим «в ряд» инструкции четырёх ВП: ${\displaystyle (\gamma -t)}$, ${\displaystyle (\sigma -f)}$, ${\displaystyle (\gamma ^{-1}-t)}$, ${\displaystyle (\sigma ^{-1}-f)}$ (строим обратные по лемме 1). Если одна или обе функции выдают 0, то результат большой программы ${\displaystyle \varepsilon =id}$: например, при ${\displaystyle f=0,t=1,\varepsilon =id{\sigma }id{\sigma }^{-1}=id}$. Если обе функции выдают 1, то ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}}$. Здесь ${\displaystyle \gamma \sigma \gamma ^{-1}\sigma ^{-1}\neq id<=>\gamma \sigma \neq \sigma \gamma }$, что верно из-за того, что эти перестановки 5-цикличны (из-за неразрешимости группы симметрии ${\displaystyle S_{5}}$). Длина новой ВП высчитывается по определению.

${\displaystyle }$ Доказательство теоремы

Будем доказывать по индукции. Предположим, что у нас есть схема C с входами ${\displaystyle x_{1},...,x_{n}}$ и что для всех подсхем D и 5-цикличных перестановок ${\displaystyle \sigma }$ существует ВП, ${\displaystyle \sigma }$-вычисляющая D. Покажем, что для всех 5-перестановок ${\displaystyle \sigma }$ существует ВП, ${\displaystyle \sigma }$-вычисляющий C.

• Если схема C выдает ${\displaystyle x_{i}}$, то ВП имеет одну инструкцию: проверить значение ${\displaystyle x_{i}}$ (0 или 1), и отдать ${\displaystyle id}$ или ${\displaystyle \sigma }$ (соответственно).
• Если схема C выдает ${\displaystyle \neg }$A для какой-то другой схемы A, по примечанию к лемме 1 создадим ВП, ${\displaystyle \sigma }$-вычисляющую ${\displaystyle \neg }$A.
• Если схема C выдает A${\displaystyle \wedge }$B для схем A и B, создадим нужную ВП по лемме 2.

Размер итоговой ветвящейся программы не превосходит ${\displaystyle 4^{d}}$, где ${\displaystyle d}$ — это глубина схемы. Если у схемы логарифмическая глубина, то у ВП полиномиальная длина.