Traccia F04

31 maggio 2016, prova 04

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

0/7
  1. 1

    Supponiamo che co-QSAT2\mathrm{co\text{-}QSAT}_2 sia riducibile a QSAT1\mathrm{QSAT}_1. CLIQUE è EXP-completo?

  2. 2

    CLIQUE∈Σ1P\mathrm{CLIQUE} \in \Sigma_1^{\mathrm{P}}?

  3. 3

    È vero che 3-COL non appartiene a Σ1P\Sigma_1^{\mathrm{P}}?

  4. 4

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

  5. 5

    Se un problema si risolve nondeterministicamente in tempo 2n2^n, si risolve con un algoritmo deterministico in spazio 2n2^n?

  6. 6

    PH=4-EXP\mathrm{PH} = 4\text{-}\mathrm{EXP}?

  7. 7

    Π4P⊆Π1P\Pi_4^{\mathrm{P}} \subseteq \Pi_1^{\mathrm{P}}?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che calcola il resto della divisione per 2 di una cifra binaria

Il metodo, passo per passo