Traccia G20v2

23 giugno 2020, versione 2

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

0/7
  1. 1

    Assumiamo che Σ2P\Sigma_2^{\mathrm{P}} e Π2P\Pi_2^{\mathrm{P}} coincidano. Dire se Π2P\Pi_2^{\mathrm{P}} non è strettamente contenuto in Σ2P\Sigma_2^{\mathrm{P}}

  2. 2

    Dire se 3-EXP e DP sono diverse

  3. 3

    Dire se VALIDITY è P-hard

  4. 4

    Dire se Σ1P⊂PP\Sigma_1^{\mathrm{P}} \subset \mathrm{PP}

  5. 5

    Tutti i linguaggi che sono accettati da MdT nondeterministiche sono anche accettati da MdT deterministiche

  6. 6

    Per ripristinare in ambito quantistico la complessità classica degli attacchi a forza bruta alla crittografia simmetrica, bisogna allungare esponenzialmente le chiavi

  7. 7

    Dire se co-QSAT3\mathrm{co\text{-}QSAT}_3 è P-hard

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che moltiplica una cifra binaria per 4

Il metodo, passo per passo
#StatoLeggeNuovo statoScriveMossaCommento
1
2
3

Da controllare

  • Riga 3: lo stato q non ha righe: lì la macchina si blocca e rigetta
Nastro
▷101⊔⊔⊔⊔
Stato sPasso 0

Prossima transizione (riga 1): δ(s, ▷) = (s, ▷, →) · supera l'inizio del nastro