Изменения

Перейти к: навигация, поиск
Нет описания правки
# Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
# Докажите, что $BPP \subset BP\cdot NP$.
# Докажите, что $BP\cdot NP \subset \Sigma_3$.
# Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.
# Определим класс $BPL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $P(M(x) = [x \in L]) \ge 2/3$. Докажите, что $BPL \subset P$.
# Докажите, что $BPL \subset SC$.
Анонимный участник

Навигация