Изменения

Перейти к: навигация, поиск

Классы NC и AC

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

Навигация