Traccia F05

31 maggio 2016, prova 05

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

0/7
  1. 1

    È falso che 4-EXP⊆Σ3P4\text{-}\mathrm{EXP} \subseteq \Sigma_3^{\mathrm{P}}?

  2. 2

    Assumiamo che Σ1P\Sigma_1^{\mathrm{P}} e Π1P\Pi_1^{\mathrm{P}} coincidano. È falso che coNP⊆PP\mathrm{coNP} \subseteq \mathrm{PP}?

  3. 3

    Un problema risolubile in spazio f(n)f(n) non può essere risolto in spazio 1722f(n)+2\frac{1}{722} f(n) + 2?

  4. 4

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

  5. 5

    GEOGRAPHY appartiene a PP?

  6. 6

    È vero che QSAT1\mathrm{QSAT}_1 non è L-hard?

  7. 7

    QSAT è P-hard?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che divide una cifra binaria per 2

Il metodo, passo per passo