Изменения
Нет описания правки
# Докажите, что $EXACTINDSET \in \Pi_2$
# Сделайте вывод про место $DP$ в полиномиальной иерархии.
# Докажите, что для любого $k > 0$ в $PH$ найдется язык, со схемной сложностью $\Omega(n^k)$.
# Докажите, что для любого $k > 0$ в $\Sigma_2$ найдется язык, со схемной сложностью $\Omega(n^k)$.
# Докажите, что если $EXP \subset P/poly$, то $EXP = \Sigma_2$.
# Докажите, что если $P=NP$, то в $EXP$, есть язык со схемной сложностью $\Omega(2^n/n)$.
# Докажите, что $SPARSE \subset P/poly$ ($SPARSE$ - множество языков, которые имеют лишь полиномиальное число слов каждой длины).
# Докажите, что умножение матриц лежит в $\widetilde{NC}$ (напомним, что $\tilde{C}$ - множество функций, для которых существует программа/схема, удовлетворяющая оценкам для $C$).
# Выведите из предыдущего задания, что $PATH \in NC$.
# Выведите из предыдущего задания, что $NL \subset NC$.
# Докажите, что $L = NC^1$ ($L$ здесь log space).
