31
правка
Изменения
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{NC^i}</tex> — множество языков, распознаваемых семейством логических схем полиномиального от <tex>n</tex> размера, глубиной <tex>O(\log^i (n))</tex> и со степенью входа каждого элемента не более 2, причем существует детерминированная машина Тьюринга, принимающая на вход <tex>1^n</tex> и строящая соответствующую схему используя <tex>O(\log(n))</tex> ячеек памяти, где <tex>n</tex> — длина входа.
}}
[[Файл:AndCircuit.png|500px|center]]
При такой замене глубина схемы увеличится не более чем в <tex>\log_2 r(n) = O(\log(n))</tex> раз, а так как изначально глубина схемы была <tex>O(\log^i(n))</tex>, то после замены всех элементов она станет <tex>O(\log^i(n)) \cdot O(\log(n)) = O(\log^{i+1}(n))</tex>.<br/>
При замене одного элемента будет добавлено не более <tex>r(n)</tex> элементов, потому, поскольку изначальный размер схемы был полиномиальным и каждый элемент мы заменили полиномиальным числом элементов, после всех замен размер схемы останется полиномиальным.
}}
|statement=<tex>\mathrm{NC} \subseteq \mathrm{P}</tex>.
|proof =
Пусть <tex>L \in \mathrm{NC}</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> таких, что существует детерминированная машина Тьюринга, строящая схему по <tex>1^n</tex>, используя <tex>O(\log(n))</tex> ячеек памяти. Конфигурация МТ задается положением головки и состоянием ячеек памяти, то есть у МТ может быть <tex>n \cdot 2^{O(\log(n))} = O(n^2)</tex> конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно схема будет построена за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим её. На вычисление схемы будет затрачено полиномиальное время, так как размер схемы полиномиален.}}
Равенство <tex>\mathrm{NC}</tex> и <tex>\mathrm{P}</tex> — неразрешенная на данный момент задача.
|about=тезис о связи <tex>\mathbf{NC}</tex> с параллельными алгоритмами
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(\log(n))</tex> тогда и только тогда, когда <tex>L \in \mathrm{NC}</tex>.
|proof=
''(набросок доказательства)''
Пусть <tex>L \in \mathrm{NC}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex>, где <tex>C_n</tex> размера <tex>N=O(poly(n))</tex> и имеет глубину <tex>O(\log^d n)</tex>. Возьмем параллельный компьютер с <tex>N</tex> процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполняться параллельно. Тогда получаем, что всего потребуется <tex>O(\log^d(n))</tex> времени.
Пусть <tex>L</tex> распознается параллельным компьютером с <tex>N=O(poly(n))</tex> процессоров за время <tex>D=O(\log^d n)</tex>. Построим схему глубины <tex>D</tex>, на каждом уровне которой будет по <tex>N</tex> элементов, таких, что <tex>i</tex>-й элемент на уровне <tex>t</tex> выполняет вычисления, производимые <tex>i</tex>-м процессором в момент времени <tex>t</tex>. Всего в схеме будет <tex>N \cdot D = O(poly(n)) \cdot O(\log^d n) = O(poly(n))</tex> элементов.
}}
[[Категория: Теория сложности]]
