Основы вычислимости и теории сложности. Лекция 12
ЛекцияПартнёр:
Предмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
05.12.12
Дата публикации:
05.12.12
Код для блога:
Схемы и параллельные вычисления
Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). Равномерные схемы. Классы NC и NCi. P-полные задачи. Соотношение между NC1, LL, NLNL и NC2. Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.
Страница лекции на сайте Computer Science Center
Другие лекции курса
11