Traccia F14

15 giugno 2017, prova 14

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

0/7
  1. 1

    È vero che 3-COL non è 3-EXP-hard?

  2. 2

    Supponiamo VALIDITY riducibile a TSP(D). È vero che EXACT TSP non è Σ2P\Sigma_2^{\mathrm{P}}-completo?

  3. 3

    NPSPACE⊂Π1P\mathrm{NPSPACE} \subset \Pi_1^{\mathrm{P}}?

  4. 4

    Le risposte a TSP(D) ammettono certificati succinti?

  5. 5

    L∈PPL \in \mathrm{PP}: è noto un metodo per ridurre l'errore in tempo polinomiale?

  6. 6

    È vero che QSAT1\mathrm{QSAT}_1 non appartiene a Σ4P\Sigma_4^{\mathrm{P}}?

  7. 7

    TSP(D) è Π1P\Pi_1^{\mathrm{P}}-hard?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che incrementa di 1 una cifra binaria

Il metodo, passo per passo