Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Схемы и параллельные вычисления
Основы вычислимости и теории сложности

Что: Лекция
Когда: Среда, 05 декабря 2012, 18:30–19:50
Где: ПОМИ РАН

Описание

Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). Равномерные схемы. Классы NC и NC. P-полные задачи. Соотношение между NC, L, NL и NC. Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.