Traccia F06

31 maggio 2016, prova 06

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

0/7
  1. 1

    Σ4P\Sigma_4^{\mathrm{P}} non è strettamente contenuto in 3-EXP?

  2. 2

    Riduzione da co-QSAT2\mathrm{co\text{-}QSAT}_2 a 2-SAT?

  3. 3

    Supponiamo Σ4P=Π4P\Sigma_4^{\mathrm{P}} = \Pi_4^{\mathrm{P}}. Σ4P\Sigma_4^{\mathrm{P}} non è strettamente contenuto in Π4P\Pi_4^{\mathrm{P}}?

  4. 4

    È falso che PSPACE⊆3-EXP\mathrm{PSPACE} \subseteq 3\text{-}\mathrm{EXP}?

  5. 5

    P≠4-EXP\mathrm{P} \neq 4\text{-}\mathrm{EXP}?

  6. 6

    La validità di una formula del primo ordine è in RE?

  7. 7

    Nondet. spazio f(n)f(n) ⇒\Rightarrow det. tempo klog⁡n+f(n)k^{\log n + f(n)}?

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