Программа курса

«Сложность параллельных вычислений»

(ФИИТ4+остальные)

1.  Введение. Булевы функции и булевы схемы. Размер и глубина схемы. Семейства булевых функций. Ограниченные и неограниченные базисы. «Стандартные» базисы B0 и B1. Length-respecting (LR) функции. Вычисление LR-функций семействами булевых схем. Пример: семейство схем постоянной глубины для сложения двоичных чисел.

2.  Классы параллельной (схемной) сложности. Классы языков (= семейств булевых функций) SIZE, DEPTH, SIZE-DEPTH. Приставки F (функциональный) и U (неограниченный).

3.  Примеры вычисления функций. Схемы для итерированного сложения, суммы входных битов, умножения, большинства, умножения и транзитивного замыкания матриц.

4.  Сводимость с постоянной глубиной. Определение и свойства сводимости. Функции, эквивалентные функции большинства (ITADD, MULT, BCOUNT, SORT).

5.  Асимптотические оценки сложности n-местных булевых функций. Нижняя оценка: теорема Шеннона. Верхняя оценка: теорема Лупанова.

6.  Сравнение с классической моделью вычислений. Вычисление невычислимых (по Тьюрингу) функций булевыми схемами. Вложение классов TIME, FTIME в классы SIZE, FSIZE и классов NSPACE в классы DEPTH.

7.  Машины Тьюринга с советом. Слэш-классы, в том числе P/Poly. Вложение классов SIZE в классы TIME/F. Равенство SIZE(nO(1)) = P/Poly.

8.  Регулярные (uniform) семейства схем. Разные условия регулярности: сложность вычисления схем из семейства машиной Тьюринга. «Регулярные» классы схемной сложности, их связь с классами TIME и SPACE (без д-ва).

9.  Нижние оценки сложности булевых функций. Существенные переменные. Общая нижняя оценка n-1 в базисе B2 и ее достижимость. Метод элиминации гейтов. Оценка для пороговой функции. Оценка в базисе U2 для функции четности.

10.  Полиномиальный метод. Персептроны и их связь с булевыми схемами. Представление булевых функций полиномами над Z, связь с представлением персептронами. Нижняя оценка на степень персептрона/полинома для функции четности.

11.  Полиномы над конечными полями. Функция MODm. Представление (в том числе, приближенное) булевых функций полиномами над конечными полями. Теорема Разборова-Смоленского.

12.  Иерархия классов схемной сложности. Классы NCi и ACi, включения между ними. Класс NC. Классы ACC(m), TC0. Основные открытые проблемы о совпадении/несовпадении классов сложности.

Основная литература:

H. Vollmer, Introduction to circuit complexity. Springer, 1999.

Еще можно заглянуть в:

H. Straubing, Finite automata, formal logic, and circuit complexity, Birkhäuser, 1994

Y. Li. Lecture 5: Razborov-Smolensky Lower Bounds for Constant-Depth Circuit with MODp Gates. 2014