Пятница, 29 января, ауд. 106. Начало в 18:00.
Докладчик: С. Нурк (СПбГУ).
Тема: О сложности задачи схемной выполнимости.
Мы поговорим о сложности задачи CircuitSat по отношению к OP(T(.)) алгоритмам (вероятностным алгоритмам с односторонней ошибкой, которым дается время T(.)).
Нашим основным приемом будет техника увеличения вероятности, основаная на следующей лемме (Exponential Amplification Lemma):
Пусть есть семейство вероятностных схем (размер которого ограничен
некоторой функцией
), решающее CircuitSat на входах,
являющихся схемами размера
c
переменными, с вероятностью
, для
. Тогда найдется семейство вероятностных схем
,
решающее CircuitSat с вероятностью
, используя размер
схемы размера
.
Используя эту лемму мы докажем строгие оценки на вероятность успешного
решения CircuitSat в нескольких моделях вычислений, в условиях
некоторых сложностных гипотез. Например, мы покажем, что при
использовании полиномиальных вероятностных схем для решения
CircuitSat, вероятность успеха не сможет превысить . В
противном случае CircuitSat (а вместе с ней и все задачи из NP),
сможет быть решена с использованием детерминированных схем размера
,
, что считается весьма мало вероятным.