Traccia F02

30 maggio 2016, prova 02

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

0/7
  1. 1

    È vero che MAX FLOW non è EXP-hard?

  2. 2

    Anche se L1≤L2L_1 \le L_2 e L2≤L3L_2 \le L_3, non è detto che L1≤L3L_1 \le L_3

  3. 3

    È vero che CLIQUE non appartiene a NEXP?

  4. 4

    coNP non è strettamente contenuto in L?

  5. 5

    EXP=Π1P\mathrm{EXP} = \Pi_1^{\mathrm{P}}?

  6. 6

    Esistono problemi in nondet. spazio f(n)f(n) non in det. tempo klog⁡n+f(n)k^{\log n + f(n)}?

  7. 7

    Supponete che co-QSAT2\mathrm{co\text{-}QSAT}_2 non sia PH-hard. PSPACE=Π2P\mathrm{PSPACE} = \Pi_2^{\mathrm{P}}?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che calcola il resto della divisione per 2 di una cifra binaria

Il metodo, passo per passo