31
правка
Изменения
Нет описания правки
==Введение==
Хотелось бы распараллелить полиномиальные вычисления. То есть? имея <tex>poly(n)</tex> процессоров? выполнять вычисления не за <tex>poly(n)</tex> времени, а за <tex>poly(\log(n))</tex>. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.
==Определения==
{{Определение
