Что: | Лекция |
Когда: | Среда, 05 декабря 2012, 18:30–19:50 |
Где: | ПОМИ РАН |
Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана). Равномерные схемы. Классы \(NC\) и \(NC^i\). P-полные задачи. Соотношение между \(NC^1\), \(L\), \(NL\) и \(NC^2\). Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.