Traccia F07

31 maggio 2016, prova 07

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

0/7
  1. 1

    2-EXP⊆Σ2P2\text{-}\mathrm{EXP} \subseteq \Sigma_2^{\mathrm{P}}?

  2. 2

    Riduzione da SAT-UNSAT a co-QSAT3\mathrm{co\text{-}QSAT}_3?

  3. 3

    L∈BPPL \in \mathrm{BPP}: l'errore si riduce sotto una soglia prefissata in tempo polinomiale?

  4. 4

    Supponiamo Π1P=Π4P\Pi_1^{\mathrm{P}} = \Pi_4^{\mathrm{P}}. NEXP⊆Π1P\mathrm{NEXP} \subseteq \Pi_1^{\mathrm{P}}?

  5. 5

    Problemi non risolubili in spazio n2n^2 ma in spazio n2⋅2log⁡nn^2 \cdot 2 \log n?

  6. 6

    CLIQUE∈Σ1P\mathrm{CLIQUE} \in \Sigma_1^{\mathrm{P}}?

  7. 7

    QSAT∈Π2P\mathrm{QSAT} \in \Pi_2^{\mathrm{P}}?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che divide una cifra binaria per 2

Il metodo, passo per passo