Traccia F12

7 giugno 2016, prova 12

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

0/7
  1. 1

    Esistono problemi risolubili nondeterministicamente in spazio nn ma non deterministicamente in tempo k2nk^{2n}?

  2. 2

    Esiste una riduzione da co-QSAT1\mathrm{co\text{-}QSAT}_1 a 3-COL?

  3. 3

    I problemi risolubili in tempo polinomiale con un algoritmo quantistico a errore limitato richiedono, su un calcolatore tradizionale, spazio O(nk)O(n^k)?

  4. 4

    PH non è strettamente contenuto in BPP?

  5. 5

    Supponiamo che co-QSAT2\mathrm{co\text{-}QSAT}_2 sia riducibile a co-QSAT1\mathrm{co\text{-}QSAT}_1. NP non è strettamente contenuto in DP?

  6. 6

    Π1P⊆coNP\Pi_1^{\mathrm{P}} \subseteq \mathrm{coNP}?

  7. 7

    3-EXP non è strettamente contenuto in BPP?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT deterministica a 2 nastri che controlla se una stringa è palindroma

Il metodo, passo per passo