Теория сложности доказательств преимущественно изучает, насколько простыми могут быть формальные доказательства интересных истинных утверждений в различных системах доказательств. Я постараюсь рассказать на простом языке и с различными примерами (доказательства не планируются) о некоторых основных идеях, результатах и открытых вопросах теории сложности доказательств. Особое внимание будет уделено её связям со смежными областями, такими как математическая логика, сложность вычислений, SAT-решатели, комбинаторная оптимизация, элементарная алгебраическая и полуалгебраическая геометрия и т.д.…

В математике автомат — это не оружие и не устройство. Это — направленный граф с n вершинами, ребра которого раскрашены в k цветов. Из каждой вершины выходят ровно k ребер, по одному каждого цвета. Конечная последовательность цветов называется «словом перезагрузки», если, выходя из произвольной вершины и проходя по ребрам соответствующих цветов, мы оказываемся в одном и том же месте. Таким образом, последовательность команд (цветов) задает перезагрузку системы: она приходит в одно и то же состояние (вершину), не зависимо от того, в каком состоянии находилась.

Как понять, есть ли у графа слово перезагрузки, и если да — то какой длины?…

Более-менее очевидно, что плотнейший способ разместить непересекающиеся круги на бесконечной плоскости — тот, при котором их центры образуют треугольную решётку (…). Задача о плотнейшей упаковке непересекающихся шаров в размерности 3 — задача Кеплера — была решена Томасом Хейлсом уже на рубеже втрого и третьего тысячелетий. Работы Марины Вязовской, решившей задачу о плотнейшей упаковке шаров в размерности 8 и — с соавторами — в размерности 24, принесли ей премию Филдса (а ответы в этих размерностях — это знаменитые решётка E_8 — решётка Коркина—Золотарёва — и решётка Лича). А что происходит в других, сильно больших размерностях?

Я расскажу, как в этой задаче взаимодействуют как взаимодействуют различные области математики — геометрия, анализ, алгебраическая геометрия и теория чисел…

Если совсем коротко: BU — это грассманиан. Однако, если заставить толпу грассманианов летать по отрезку, то получается снова U, просто по спектральной теореме. Отсюда и периодичность. Красиво же!