Traccia MA23

14 marzo 2023

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

0/7
  1. 1

    È vero che 2-SAT non può essere deciso da una MdT nondeterministica in spazio polinomiale?

  2. 2

    2-COL è PH-hard?

  3. 3

    GEOGRAPHY è NL-hard?

  4. 4

    Con 2 nastri in tempo f(n)f(n) ⇒\Rightarrow 1 nastro in tempo f(n)2f(n)^2?

  5. 5

    Spazio n3n^3 ⇒\Rightarrow spazio n3⋅3log⁡nn^3 \cdot 3 \log n?

  6. 6

    EXP⊂DP\mathrm{EXP} \subset \mathrm{DP}?

  7. 7

    Supponiamo BPP=Σ2P\mathrm{BPP} = \Sigma_2^{\mathrm{P}}. 3-COL si risolve in tempo polinomiale con errore limitato?

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