Изменения

# Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.

# Докажите, что $BPP \subset BP\cdot NP$.

# Докажите, что если $\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$.