Home

Пятница, 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):

Пусть есть семейство вероятностных схем $ A $ (размер которого ограничен некоторой функцией $ f(n, m) $), решающее CircuitSat на входах, являющихся схемами размера $ m $ c $ n $ переменными, с вероятностью $ \ge 2^{−\alpha n} $, для $ \alpha<1 $. Тогда найдется семейство вероятностных схем $ B $, решающее CircuitSat с вероятностью $ \ge 2^{−\alpha^2 n} $, используя размер схемы размера $ f(αn, f(m,n)) $.

Используя эту лемму мы докажем строгие оценки на вероятность успешного решения CircuitSat в нескольких моделях вычислений, в условиях некоторых сложностных гипотез. Например, мы покажем, что при использовании полиномиальных вероятностных схем для решения CircuitSat, вероятность успеха не сможет превысить $ 2^{−n+o(n)} $. В противном случае CircuitSat (а вместе с ней и все задачи из NP), сможет быть решена с использованием детерминированных схем размера $ 2^{n^\mu} $, $ \mu < 1 $, что считается весьма мало вероятным.