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

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

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

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

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

Страница курса на сайте CS Club