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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теоремы)
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 8 участников)
Строка 1: Строка 1:
 +
Предположим у нас есть компьютер с <tex>poly(n)</tex> процессоров. Тогда актуально распараллелить полиномиальные вычисления, чтобы выполнять их не за <tex>poly(n)</tex> времени, а за <tex>poly(\log(n))</tex>. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.
 +
 
==Определения==
 
==Определения==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>NC^i = \mathcal{f} L \mid L — </tex> распознается семейством логических схем размера полином от <tex>n</tex> и глубины <tex>O(log^i (n))</tex>, где <tex>n</tex> — длина входа; степень входа элемента не больше двух. Причем такую схему можно построить по <tex>1^n</tex> на <tex>O(log(n))</tex> памяти.
+
<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> — длина входа.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, за исключением того, что степень входа элемента может быть неограничена, то есть элементы <tex>\mathrm{OR}</tex> и <tex>\mathrm{AND}</tex> могут иметь более двух входов.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>AC^i</tex> определяется аналогично <tex>NC^i</tex>, только степень входа элемента неограничена.
+
<tex>\mathrm{NC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>NC = \cup^{\infty}_{i = 0} NC^i</tex><br/>
+
<tex>\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}</tex>.
<tex>AC = \cup^{\infty}_{i = 0} AC^i</tex><br/>
 
 
}}
 
}}
  
 
==Теоремы==
 
==Теоремы==
 
{{Теорема
 
{{Теорема
|statement=<tex>NC^i \subset AC^i \subset NC^{i+1}</tex>
+
|statement=<tex>\mathrm{NC^i} \subset \mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex>.
 
|proof=
 
|proof=
*<tex>NC^i \subset AC^i</tex> <br/>
+
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> <br/>
Это очевидно из определения <tex>NC^i</tex> и <tex>AC^i</tex>. <br/>
+
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/>
*<tex>AC^i \subset NC^{i+1}</tex> <br/>
+
*<tex>\mathrm{AC^i} \subset \mathrm{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> элементами со степенью входа не более двух следующим образом: <br/>
+
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Степень входа каждого элемента схемы <tex>C_n</tex> не превосходит полинома от <tex>n</tex>, поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более 2 следующим образом:
[[Файл:circuit.jpg]]
+
 
При замене каждого такого элемента глубина будет увеличиваться на <tex>log_2 r(n) = O(log(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> элементов, потому, поскольку изначальный размер схемы был полиномиальным и каждый элемент мы заменили полиномиальным числом элементов, после всех замен размер схемы останется полиномиальным.
 
}}
 
}}
'''Следствие:'''  <tex>NC = AC</tex><br/>
+
'''Следствие:'''  <tex>\mathrm{NC} = \mathrm{AC}</tex>.
  
 
   
 
   
 
{{Теорема
 
{{Теорема
|statement=<tex>NC \subseteq P</tex>
+
|statement=<tex>\mathrm{NC} \subseteq \mathrm{P}</tex>.
 
|proof =
 
|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> время. Построим для данного входа схему и вычислим ее.}}
+
Пусть <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>NC</tex> и <tex>P</tex> — неразрешенная на данный момент задача.
+
Равенство <tex>\mathrm{NC}</tex> и <tex>\mathrm{P}</tex> — неразрешенная на данный момент задача.
  
  
{{Теорема
+
{{Утверждение
 +
|about=тезис о связи <tex>\mathbf{NC}</tex> с параллельными алгоритмами
 
|statement=
 
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n)) \Leftrightarrow L \in NC</tex>.
+
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(\log (n))</tex> тогда и только тогда, когда <tex>L \in \mathrm{NC}</tex>.
 
|proof=
 
|proof=
Пусть <tex>L \in 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>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> элементов.
 
}}
 
}}
 +
 +
[[Категория:Классы сложности]]

Текущая версия на 19:21, 4 сентября 2022

Предположим у нас есть компьютер с [math]poly(n)[/math] процессоров. Тогда актуально распараллелить полиномиальные вычисления, чтобы выполнять их не за [math]poly(n)[/math] времени, а за [math]poly(\log(n))[/math]. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.

Определения

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


Определение:
[math]\mathrm{AC^i}[/math] определяется аналогично [math]\mathrm{NC^i}[/math], за исключением того, что степень входа элемента может быть неограничена, то есть элементы [math]\mathrm{OR}[/math] и [math]\mathrm{AND}[/math] могут иметь более двух входов.


Определение:
[math]\mathrm{NC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}[/math].


Определение:
[math]\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}[/math].


Теоремы

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

Это понятно из определения [math]\mathrm{NC^i}[/math] и [math]\mathrm{AC^i}[/math].

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

Пусть [math]L \in \mathrm{AC^i}[/math]. [math]L[/math] распознается семейством схем [math]C_n[/math] полиномиального размера. Степень входа каждого элемента схемы [math]C_n[/math] не превосходит полинома от [math]n[/math], поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы [math]C_n[/math] элементами со степенью входа не более 2 следующим образом:

AndCircuit.png

При такой замене глубина схемы увеличится не более чем в [math]\log_2 r(n) = O(\log(n))[/math] раз, а так как изначально глубина схемы была [math]O(\log^i(n))[/math], то после замены всех элементов она станет [math]O(\log^i(n)) \cdot O(\log(n)) = O(\log^{i+1}(n))[/math].

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

Следствие: [math]\mathrm{NC} = \mathrm{AC}[/math].


Теорема:
[math]\mathrm{NC} \subseteq \mathrm{P}[/math].
Доказательство:
[math]\triangleright[/math]
Пусть [math]L \in \mathrm{NC}[/math]. Тогда [math]L[/math] распознается некоторым семейством схем [math]C_n[/math] таких, что существует детерминированная машина Тьюринга, строящая схему по [math]1^n[/math], используя [math]O(\log (n))[/math] ячеек памяти. Конфигурация МТ задается положением головки и состоянием ячеек памяти, то есть у МТ может быть [math]n \cdot 2^{O(\log (n))} = O(n^2)[/math] конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно схема будет построена за полиномиальное от [math]n[/math] время. Построим для данного входа схему и вычислим её. На вычисление схемы будет затрачено полиномиальное время, так как размер схемы полиномиален.
[math]\triangleleft[/math]

Равенство [math]\mathrm{NC}[/math] и [math]\mathrm{P}[/math] — неразрешенная на данный момент задача.


Утверждение (тезис о связи [math]\mathbf{NC}[/math] с параллельными алгоритмами):
[math]L[/math] распознается параллельным компьютером с [math]O(poly(n))[/math] процессоров за время [math]O(poly(\log (n))[/math] тогда и только тогда, когда [math]L \in \mathrm{NC}[/math].
[math]\triangleright[/math]

(набросок доказательства)

Пусть [math]L \in \mathrm{NC}[/math]. [math]L[/math] распознается семейством схем [math]C_n[/math], где [math]C_n[/math] размера [math]N=O(poly(n))[/math] и имеет глубину [math]O(\log^d n)[/math]. Возьмем параллельный компьютер с [math]N[/math] процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполняться параллельно. Тогда получаем, что всего потребуется [math]O(\log^d(n))[/math] времени.

Пусть [math]L[/math] распознается параллельным компьютером с [math]N=O(poly(n))[/math] процессоров за время [math]D=O(\log^d n)[/math]. Построим схему глубины [math]D[/math], на каждом уровне которой будет по [math]N[/math] элементов, таких, что [math]i[/math]-й элемент на уровне [math]t[/math] выполняет вычисления, производимые [math]i[/math]-м процессором в момент времени [math]t[/math]. Всего в схеме будет [math]N \cdot D = O(poly(n)) \cdot O(\log^d n) = O(poly(n))[/math] элементов.
[math]\triangleleft[/math]