Изменения
Новая страница: «==Определения== {{Определение |definition= <tex>NC^i = \mathcal{f} L \mid L — </tex> распознается семейством схе...»
==Определения==
{{Определение
|definition=
<tex>NC^i = \mathcal{f} L \mid L — </tex> распознается семейством схем со степенью входа элемента не больше двух, размера <tex>poly(n)</tex> и глубины <tex>O(log^i (n))</tex> где <tex>n</tex> размер входа. Причем такую схему можно построить по <tex>1^n</tex> на <tex>O(log(n))</tex> памяти.
}}
{{Определение
|definition=
<tex>AC^i</tex> определяется аналогично <tex>NC^i</tex>, только степень входа элемента неограничена.
}}
{{Определение
|definition=
<tex>NC = \cup^{\infty}_{i = 0} NC^i</tex><br/>
<tex>AC = \cup^{\infty}_{i = 0} AC^i</tex><br/>
}}
==Теоремы==
{{Теорема
|statement=<tex>NC^i \subset AC^i \subset NC^{i+1}</tex>
|proof=
*<tex>NC^i \subset AC^i</tex> <br/>
Это очевидно из определения <tex>NC^i</tex> и <tex>AC^i</tex>. <br/>
*<tex>AC^i \subset NC^{i+1}</tex> <br/>
Пусть <tex>L \in AC^i</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит степень входа у элементов схемы <tex>C_n</tex> это полином <tex>r(n)</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом:
При замене каждого такого элемента размер схемы будет оставаться полиномиальным, а глубина увеличится на <tex>log_2 r(n) = O(log(n))</tex>.
}}
'''Следствие:''' <tex>NC = AC</tex><br/>
'''Тезис'''<br/>
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n)) \Leftrightarrow L \in NC</tex>.
{{Теорема
|statement=<tex>NC \subseteq P</tex>
|proof =
Пусть <tex>L \in NC</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> которые по <tex>1^n</tex> можно построить на <tex>O(log(n))</tex> памяти и, следовательно, за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим ее.}}
{{Определение
|definition=
<tex>NC^i = \mathcal{f} L \mid L — </tex> распознается семейством схем со степенью входа элемента не больше двух, размера <tex>poly(n)</tex> и глубины <tex>O(log^i (n))</tex> где <tex>n</tex> размер входа. Причем такую схему можно построить по <tex>1^n</tex> на <tex>O(log(n))</tex> памяти.
}}
{{Определение
|definition=
<tex>AC^i</tex> определяется аналогично <tex>NC^i</tex>, только степень входа элемента неограничена.
}}
{{Определение
|definition=
<tex>NC = \cup^{\infty}_{i = 0} NC^i</tex><br/>
<tex>AC = \cup^{\infty}_{i = 0} AC^i</tex><br/>
}}
==Теоремы==
{{Теорема
|statement=<tex>NC^i \subset AC^i \subset NC^{i+1}</tex>
|proof=
*<tex>NC^i \subset AC^i</tex> <br/>
Это очевидно из определения <tex>NC^i</tex> и <tex>AC^i</tex>. <br/>
*<tex>AC^i \subset NC^{i+1}</tex> <br/>
Пусть <tex>L \in AC^i</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит степень входа у элементов схемы <tex>C_n</tex> это полином <tex>r(n)</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом:
При замене каждого такого элемента размер схемы будет оставаться полиномиальным, а глубина увеличится на <tex>log_2 r(n) = O(log(n))</tex>.
}}
'''Следствие:''' <tex>NC = AC</tex><br/>
'''Тезис'''<br/>
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n)) \Leftrightarrow L \in NC</tex>.
{{Теорема
|statement=<tex>NC \subseteq P</tex>
|proof =
Пусть <tex>L \in NC</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> которые по <tex>1^n</tex> можно построить на <tex>O(log(n))</tex> памяти и, следовательно, за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим ее.}}
