1632
правки
Изменения
м
rollbackEdits.php mass rollback
Предположим у нас есть компьютер с <tex>poly(n)</tex> процессоров. Тогда актуально распараллелить полиномиальные вычисления, чтобы выполнять их не за <tex>poly(n)</tex> времени, а за <tex>poly(\log(n))</tex>. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.
==Определения==
{{Определение
{{Определение
|definition=
<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, за исключением того, что степень входа элемента может быть неограничена, то есть элементы <tex>\mathrm{OR}</tex> и <tex>\mathrm{AND}</tex> могут иметь более двух входов.
}}
}}
[[Категория: Теория Классы сложности]]
