Traccia G17

23 giugno 2017

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

0/7
  1. 1

    Se scoprissimo che P≠NP\mathrm{P} \neq \mathrm{NP}, sapremmo dire se esistono funzioni one-way?

  2. 2

    Supponiamo P⊂Σ3P\mathrm{P} \subset \Sigma_3^{\mathrm{P}}. È vero che 2-SAT non è Σ3P\Sigma_3^{\mathrm{P}}-completo?

  3. 3

    È falso che Σ1P⊆Σ3P\Sigma_1^{\mathrm{P}} \subseteq \Sigma_3^{\mathrm{P}}?

  4. 4

    È falso che coNP⊆Π3P\mathrm{coNP} \subseteq \Pi_3^{\mathrm{P}}?

  5. 5

    PP⊂Π3P\mathrm{PP} \subset \Pi_3^{\mathrm{P}}?

  6. 6

    DP non è strettamente contenuto in Π1P\Pi_1^{\mathrm{P}}?

  7. 7

    Un problema risolubile in spazio f(n)f(n) non può essere risolto in spazio 1601f(n)+2\frac{1}{601} f(n) + 2?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT deterministica a 2 nastri che controlla se una stringa è palindroma

Il metodo, passo per passo