Mathematical Logic and Discrete Mathematics at PDMI

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

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

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

Abstract

Мы поговорим о сложности задачи 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$, что считается весьма мало вероятным.