23 giugno 2020, versione 5

Supponiamo che $\mathrm{DP} = \mathrm{NEXP}$. Dire se $\Pi_3^{\mathrm{P}} \neq \mathrm{PH}$

Dire se $\mathrm{QSAT}_2$ è riducibile a STRATEGIC COMPANIES

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

Dire se $\mathrm{UP} \subseteq \mathrm{DP}$

Tutti i linguaggi che sono accettati da MdT nondeterministiche sono anche accettati da MdT deterministiche

Sia $L$ un problema in BPP. Dire se la probabilità di errore può essere ridotta sotto una soglia prefissata in tempo polinomiale

È vero che EXACT TSP non è $\Sigma_1^{\mathrm{P}}$-hard?