Сложность булевых функций

Санкт-Петербург, осень 2014

Описание

В рамках курса планируется рассказать об одном из основных направлений теории сложности вычислений — схемной сложности булевых функций.

Формальное изучение этой области началось еще в первой половине двадцатого века, то есть очень давно по меркам Computer Science. Бум развития схемной сложности пришелся на 80-е годы и был связан с идеей использования нижних оценок размера булевых схем, как подхода к проблеме о сложностных классах P и NP. Этот этап развития области привел к ряду прорывных результатов, новых методов и идей. Однако, оказалось, что получить решение проблемы о P и NP на этом пути (как и на всех других) не так просто. Более того, было доказано, что для решения этой проблемы посредством булевых схем нужны кардинально новые методы, и текущих методов принципиально не достаточно. В настоящее время работа в области схемной сложности продолжается, в последние годы был получен ряд интересных результатов.

В курсе будет дано введение в теорию схемной сложности булевых функций, рассказано о некоторых ключевых результатах в области, а также о связях с другими моделями вычислений. Основной акцент планируется сделать на методах доказательства нижних оценок в схемной сложности. Также мы попробуем показать, как результаты теории схемной сложности, могут применяться к другим областям Computer Science, на примере вопросов о сложности обработки запросов к онтологическим базам данных.

Задачи и критерии получения оценки за курс можно найти на странице курса на сайте CS клуба. Решения задач можно слать Владимиру Подольскому до конца семестра.

Преподаватели

Список лекций

Булевы схемы и формулы

Определение булевых схем и булевых формул, введение. Взаимосвязь глубины и размера формул.

Булевы формулы и коммуникационная сложность

Характеризация глубины булевых схем с помощью коммуникационной сложности.

Монотонные формулы для задачи «Достижимость», сведение к коммуникационным играм

Начало доказательства нижней оценки \(\Omega(\log^2 n)\) глубины монотонных формул для задачи достижимости в ориентированном графе. Сведение к коммуникационной сложности.

Монотонные формулы для задачи «Достижимость», нижняя оценка

Завершение доказательства нижней оценки \(\Omega(\log^2 n)\) глубины монотонных формул для задачи достижимости в ориентированном графе. Оценка коммуникационной сложности.

Монотонные формулы для функций «Паросочетание» и «Клика»

Нижняя оценка \(\Omega(n)\) глубины монотонных формул для функций «Паросочетание» и «Клика».

Нижняя оценка для монотонных схем, начало

Начало доказательства нижней оценки \( 2^{\Omega(n^{\epsilon})} \) размера монотонных схем для функции «Клика»: функция «Клика» не приближается дизъюнкцией малого числа индикаторных функций.

Нижняя оценка для монотонных схем, окончание

Завершение доказательства нижней оценки \( 2^{\Omega(n^{\epsilon})} \) размера монотонных схем для функции «Клика»: монотонные схемы маленького размера приближаются дизъюнкцией малого числа индикаторных функций.

Приложение: онтологические базы данных

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

Схемы ограниченной глубины: приближение многочленами

Нижняя оценка \( 2^{\Omega(n^\epsilon)} \) размера схем постоянной глубины в базисе из отрицаний, конъюнкций, дизъюнкций и сложения по модулю 3, вычисляющих функцию сложения по модулю 2.

Пороговые схемы

Пороговые схемы, введение. Нижняя оценка \( n/2 \) размера пороговых схем для функции «Скалярное произведение».