Завтра, 19 апреля, состоится лекция по допглавам сложности. Начало, как обычно, в 12. Будем разбираться с теоремой MIP=NEXP. Она соединяет в себе идеи из IP=PSPACE и PCP-теоремы. Будут использованы техника тестирования и самокоррекции, многочлены малых степеней, расширение булевой функции на конечное поле и т.д.