Traccia MZ22

20 marzo 2022

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

0/7
  1. 1

    Dire se UP⊂coNP\mathrm{UP} \subset \mathrm{coNP}

  2. 2

    Supponiamo che GEOGRAPHY appartenga a DP. Dire se Π2P⊂Σ3P\Pi_2^{\mathrm{P}} \subset \Sigma_3^{\mathrm{P}}

  3. 3

    Dire se Π3P⊂Π2P\Pi_3^{\mathrm{P}} \subset \Pi_2^{\mathrm{P}}

  4. 4

    Dire se NEXP⊂Σ1P\mathrm{NEXP} \subset \Sigma_1^{\mathrm{P}}

  5. 5

    Se scoprissimo che P=NP\mathrm{P} = \mathrm{NP}, sapremmo dire se esistono o meno funzioni one-way?

  6. 6

    Se A è riducibile a B e B è riducibile a C, allora A è riducibile anche a C

  7. 7

    È vero che MAX FLOW non può essere deciso da una MdT deterministica in spazio polinomiale?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che accetta le stringhe x;yx;y, con xx e yy interi in binario della stessa lunghezza e x≤yx \le y

Il metodo, passo per passo