Traccia LU24

15 luglio 2024, prova 4

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

0/7
  1. 1

    Dire se EXP⊂PP\mathrm{EXP} \subset \mathrm{PP}

  2. 2

    Dire se 3-COL è riducibile a GEOGRAPHY

  3. 3

    Un problema risolubile in tempo f(n)f(n) da una MdT nondeterministica può essere risolto in tempo c2f(n)c^{2f(n)} da una MdT deterministica con 1 nastro?

  4. 4

    Dire se le risposte a test di soddisfacibilità di knowledge base SROIQ (OWL-2) ammettono disqualifiers succinti

  5. 5

    Assumiamo che NL e PH coincidano. Dire se coNP⊂NEXP\mathrm{coNP} \subset \mathrm{NEXP}

  6. 6

    Dire se Σ1P⊆EXP\Sigma_1^{\mathrm{P}} \subseteq \mathrm{EXP}

  7. 7

    Dire se fEXPf_{\mathrm{EXP}} è una one-way function

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che accetta le stringhe nel formato key,el1,…,eln,\mathit{key}, \mathit{el}_1, \dots, \mathit{el}_n, (l'ultima virgola è parte dell'input) con key diversa da tutti gli eli\mathit{el}_i

Il metodo, passo per passo