Traccia G20v4

23 giugno 2020, versione 4

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

0/7
  1. 1

    Supponiamo che L⊂Σ2P\mathrm{L} \subset \Sigma_2^{\mathrm{P}}. Dire se QSAT2\mathrm{QSAT}_2 è L-completo

  2. 2

    È vero che CIRC SAT non è 4-EXP-completo?

  3. 3

    Dire se EXP⊆4-EXP\mathrm{EXP} \subseteq 4\text{-}\mathrm{EXP}

  4. 4

    Dire se SCHÖNFINKEL-BERNAYS SAT è Σ3P\Sigma_3^{\mathrm{P}}-completo

  5. 5

    Dire se un problema risolubile in tempo f(n)f(n) da una MdT nondeterministica può essere risolto in tempo c2f(n)c^{2f(n)} da una MdT deterministica con 1 nastro

  6. 6

    Il controllo di soddisfacibilità di una formula logica del primo ordine è in coRE

  7. 7

    È vero che CLIQUE non appartiene a Π4P\Pi_4^{\mathrm{P}}?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT nondeterministica che controlla se una stringa non è palindroma in tempo 2n2n

Il metodo, passo per passo