Traccia SE23

15 settembre 2023

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

0/7
  1. 1

    co-QSAT1∈Σ3P\mathrm{co\text{-}QSAT}_1 \in \Sigma_3^{\mathrm{P}}?

  2. 2

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

  3. 3

    Supponiamo PH=EXP\mathrm{PH} = \mathrm{EXP}. QSAT∈PH\mathrm{QSAT} \in \mathrm{PH}?

  4. 4

    PH⊆BQP\mathrm{PH} \subseteq \mathrm{BQP}?

  5. 5

    PSPACE⊆2-EXP\mathrm{PSPACE} \subseteq 2\text{-}\mathrm{EXP}?

  6. 6

    3-COL è riducibile a QSAT4\mathrm{QSAT}_4?

  7. 7

    Nondet. tempo f(n)f(n) ⇒\Rightarrow det. spazio f(n)f(n)?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che accetta le stringhe nel formato key,el1,…,eln,\mathit{key}, \mathit{el}_1, \dots, \mathit{el}_n, (l'ultima virgola è parte dell'input) con key e gli eli\mathit{el}_i stringhe di bit e key diversa da tutti gli eli\mathit{el}_i

Il metodo, passo per passo