Несмотря на множество усилий научного сообщества всего мира, мы до сих пор не умеем объяснять, почему некоторые алгоритмические задачи не удаётся быстро решить на компьютере. Например, у нас есть очень эффективные алгоритмы проверки эйлеровости графа (есть ли в графе цикл, проходящий по всем рёбрам), но нет ни одного хоть сколько-нибудь эффективного алгоритма проверки гамильтоновости графа (наличия цикла, проходящего по всем вершинам). Действительно ли вторая задача настолько труднее первой? У нас нет такого алгоритма, потому что мы не можем его придумать или потому что его просто не существует?

Чтобы доказать, что эффективного алгоритма не существует, нужно зафиксировать вычислительную модель. Как правило для этого используется машина Тьюринга. Несмотря на свою простоту, машина Тьюринга всё-таки достаточно сложный объект: у неё есть ленты, головка, программа (практически как у реального компьютера). В то же время есть куда более простая модель вычислений — булевы схемы. Схему можно задавать двумя способами: либо как граф входящей степени два с операциями в вершинах, либо как простейшую программу, в которой нет ни ветвлений, ни циклов. Схемы, с одной стороны, достаточно мощны (если для задачи есть эффективный алгоритм, то есть и схема такой же эффективности), а с другой — настолько просто устроены, что интуитивно кажется вполне возможным доказать, что для некоторых сложных задач эффективных схем не существует.

Доказать это, однако, так и не удаётся. На лекции расскажем, что же мы умеем доказывать про схемы и что мы хотим научиться доказывать.