Traccia F01

30 maggio 2016, prova 01

Rispondi prima di leggere la spiegazione. I termini sottolineati offrono un aiuto rapido.

0/7

1
$\mathrm{PSPACE} \subseteq \mathrm{NEXP}$
2
$\Pi_2^{\mathrm{P}} \subset \mathrm{EXP}$
3
$\mathrm{P} \neq \mathrm{NP}$
4
$4\text{-}\mathrm{EXP} \neq \mathrm{L}$
5
$SCHÖNFINKEL-BERNAYS SAT decidibile in tempo polinomiale con errore limitato da una MdT quantistica ?$
6
$Le riduzioni per i function problems hanno qualcosa in più?$
7
$È vero che 2-SAT non appartiene a DP ?$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT che accetta gli interi positivi dispari (codificati in complemento a due)