7 giugno 2016, prova 11

Supponiamo $\mathrm{PH} = \mathrm{EXP}$. MAX FLOW è PH-completo?

$\Sigma_4^{\mathrm{P}} \subset \Sigma_3^{\mathrm{P}}$?

È falso che $\Sigma_3^{\mathrm{P}} \subseteq \Pi_4^{\mathrm{P}}$?

È vero che $\mathrm{QSAT}_3$ non è coNP-hard?

Risolubile con 5 nastri in tempo $f(n)$ $\Rightarrow$ non risolubile con 1 nastro in tempo $f(n)^2$?

Riduzione da QSAT a $\mathrm{co\text{-}QSAT}_3$?

Risolubile in spazio $f(n)$ $\Rightarrow$ non risolubile in spazio $(1/345) \cdot f(n) + 2$?