Traccia FE23

14 febbraio 2023

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

0/7
  1. 1

    SCHÖNFINKEL-BERNAYS SAT è PSPACE-completo?

  2. 2

    È vero che SAT non appartiene a PP?

  3. 3

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

  4. 4

    Spazio nen^e, esistono problemi non in tempo knek^{n^e}?

  5. 5

    È falso che P⊆NPSPACE\mathrm{P} \subseteq \mathrm{NPSPACE}?

  6. 6

    Esistono problemi in nondet. spazio log⁡n\log n non in det. spazio (log⁡n)2(\log n)^2?

  7. 7

    Supponiamo co-QSAT4∈Σ3P\mathrm{co\text{-}QSAT}_4 \in \Sigma_3^{\mathrm{P}}. Σ3P≠Σ4P\Sigma_3^{\mathrm{P}} \neq \Sigma_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