23 giugno 2020, versione 3

Assumiamo che DP e PH coincidano. Dire se CIRC SAT è $\Pi_3^{\mathrm{P}}$-hard

Dire se $\Sigma_2^{\mathrm{P}} \subseteq \Sigma_3^{\mathrm{P}}$

È vero che SCHÖNFINKEL-BERNAYS SAT non è $\Sigma_1^{\mathrm{P}}$-hard?

Dire se L e NL coincidono

Per ripristinare in ambito quantistico la complessità classica degli attacchi a forza bruta alla crittografia simmetrica, basta raddoppiare la lunghezza delle chiavi

I problemi risolubili in tempo polinomiale con un algoritmo quantistico a errore limitato richiedono, su di un calcolatore tradizionale, spazio $O(2^n)$

È falso che $\mathrm{NL} \subseteq \mathrm{NP}$