Пятница, 29 января, 18:00, к. 106

Пятница, 29 января, ауд. 106. Начало в 18:00.

Докладчик: С. Нурк (СПбГУ).

Тема: О сложности задачи схемной выполнимости.

Abstract

Доклад по статье Ramamohan Paturi and Pavel Pudlak "On the Complexity of Circuit Satisfiability".

Мы поговорим о сложности задачи CircuitSat по отношению к OP(T(.)) алгоритмам (вероятностным алгоритмам с односторонней ошибкой, которым дается время T(.)).

Нашим основным приемом будет техника увеличения вероятности, основаная на следующей лемме (Exponential Amplification Lemma):

Пусть есть семейство вероятностных схем

(размер которого ограничен некоторой функцией

), решающее CircuitSat на входах, являющихся схемами размера

c

переменными, с вероятностью

, для

. Тогда найдется семейство вероятностных схем

, решающее CircuitSat с вероятностью

, используя размер схемы размера

.

Используя эту лемму мы докажем строгие оценки на вероятность успешного решения CircuitSat в нескольких моделях вычислений, в условиях некоторых сложностных гипотез. Например, мы покажем, что при использовании полиномиальных вероятностных схем для решения CircuitSat, вероятность успеха не сможет превысить

. В противном случае CircuitSat (а вместе с ней и все задачи из NP), сможет быть решена с использованием детерминированных схем размера

,

, что считается весьма мало вероятным.