Изменения

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

[[Категория: Теория Классы сложности]]