Классы NC и AC — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определения== {{Определение |definition= <tex>NC^i = \mathcal{f} L \mid L — </tex> распознается семейством схе...»)
(нет различий)

Версия 00:04, 15 апреля 2012

Определения

Определение:
[math]NC^i = \mathcal{f} L \mid L — [/math] распознается семейством схем со степенью входа элемента не больше двух, размера [math]poly(n)[/math] и глубины [math]O(log^i (n))[/math] где [math]n[/math] размер входа. Причем такую схему можно построить по [math]1^n[/math] на [math]O(log(n))[/math] памяти.


Определение:
[math]AC^i[/math] определяется аналогично [math]NC^i[/math], только степень входа элемента неограничена.


Определение:
[math]NC = \cup^{\infty}_{i = 0} NC^i[/math]
[math]AC = \cup^{\infty}_{i = 0} AC^i[/math]


Теоремы

Теорема:
[math]NC^i \subset AC^i \subset NC^{i+1}[/math]
Доказательство:
[math]\triangleright[/math]
  • [math]NC^i \subset AC^i[/math]

Это очевидно из определения [math]NC^i[/math] и [math]AC^i[/math].

  • [math]AC^i \subset NC^{i+1}[/math]

Пусть [math]L \in AC^i[/math]. [math]L[/math] распознается семейством схем [math]C_n[/math] полиномиального размера. Значит степень входа у элементов схемы [math]C_n[/math] это полином [math]r(n)[/math]. Заменим элементы схемы [math]C_n[/math] элементами со степенью входа не более двух следующим образом:

При замене каждого такого элемента размер схемы будет оставаться полиномиальным, а глубина увеличится на [math]log_2 r(n) = O(log(n))[/math].
[math]\triangleleft[/math]

Следствие: [math]NC = AC[/math]


Тезис
[math]L[/math] распознается параллельным компьютером с [math]O(poly(n))[/math] процессоров за время [math]O(poly(log(n)) \Leftrightarrow L \in NC[/math].


Теорема:
[math]NC \subseteq P[/math]
Доказательство:
[math]\triangleright[/math]
Пусть [math]L \in NC[/math]. Тогда [math]L[/math] распознается некоторым семейством схем [math]C_n[/math] которые по [math]1^n[/math] можно построить на [math]O(log(n))[/math] памяти и, следовательно, за полиномиальное от [math]n[/math] время. Построим для данного входа схему и вычислим ее.
[math]\triangleleft[/math]