Traccia F13

15 giugno 2017, prova 13

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

0/7
  1. 1

    Supponiamo Π2P=PH\Pi_2^{\mathrm{P}} = \mathrm{PH}. È vero che non esistono riduzioni da QSAT4\mathrm{QSAT}_4 a co-QSAT4\mathrm{co\text{-}QSAT}_4?

  2. 2

    Le riduzioni per i function problems sono come quelle per i problemi di decisione?

  3. 3

    È vero che QSAT1\mathrm{QSAT}_1 non è NP-completo?

  4. 4

    NEXP⊆PSPACE\mathrm{NEXP} \subseteq \mathrm{PSPACE}?

  5. 5

    Nondet. spazio 2n2n ⇒\Rightarrow det. spazio (2n)2(2n)^2?

  6. 6

    QSAT è 2-EXP-completo?

  7. 7

    PSPACE⊂NPSPACE\mathrm{PSPACE} \subset \mathrm{NPSPACE}?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che moltiplica una cifra binaria per 2

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