Александр Александрович Разборов Теория сложности вычислений А.А.Разборов планирует провести 2–3 занятия.

В течении нескольких последних лет на этой школе докладчик рассказывал о различных разделах современной теории сложности, такие как квантовая (2006), коммуникационная (2009) и алгебраическая (2010) сложность. В этом году мы немного поговорим про те идеи и методы, которые все эти разнородные вещи объединяют в единую красивую науку.

Курс начнётся с краткого знакомства с тьюринговой сложностью и введения в историю вопроса P vs. NP и закончится различными иллюстрациями того, как в самых разных областях появляются идеи «измеримой эффективности», «абстрактного вычислительного устройства» и «класса сложности». Точные формулировки и, возможно, даже некоторые детали доказательств будут в основном вынесены на семинарское занятие; основной упор в самих лекциях будет сделан именно на неформальных, общих идеях.

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