Traccia L18

12 luglio 2018

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

0/7
  1. 1

    Se PH=EXP\mathrm{PH} = \mathrm{EXP}, PH collassa a un livello finito?

  2. 2

    TIME(n3)⊆TIME((2n+1)9)\mathrm{TIME}(n^3) \subseteq \mathrm{TIME}((2n+1)^9)?

  3. 3

    È falso che P⊆PH\mathrm{P} \subseteq \mathrm{PH}?

  4. 4

    QSAT∈EXP\mathrm{QSAT} \in \mathrm{EXP}?

  5. 5

    È vero che QSAT1∉2-EXP\mathrm{QSAT}_1 \notin 2\text{-}\mathrm{EXP}?

  6. 6

    CLIQUE si può risolvere in O(2n/2)O(2^{n/2})?

  7. 7

    Π4P⊆L\Pi_4^{\mathrm{P}} \subseteq \mathrm{L}?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT deterministica che, dato un valore xx binario, restituisca −x-x

Il metodo, passo per passo