23 giugno 2020, versione 1

Assumiamo che $\Sigma_3^{\mathrm{P}}$ e $\Pi_3^{\mathrm{P}}$ coincidano. Dire se $\mathrm{co\text{-}QSAT}_3$ è $\Sigma_3^{\mathrm{P}}$-completo

Dire se $\mathrm{P} = 4\text{-}\mathrm{EXP}$

Dire se $\Pi_4^{\mathrm{P}} \subset \mathrm{DP}$

Dire se 3-COL è $\Pi_2^{\mathrm{P}}$-completo

Esistono linguaggi che sono accettati da MdT nondeterministiche ma non sono in RE

Esistono problemi risolubili nondeterministicamente in tempo $f(n)$ ma non risolubili deterministicamente in spazio $f(n)$

Dire se NEXP e L sono diverse