Traccia F03

31 maggio 2016, prova 03

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

0/7
  1. 1

    co-QSAT4\mathrm{co\text{-}QSAT}_4 è riducibile a HAMILTON PATH?

  2. 2

    PRIMES è riducibile a TSP(D)?

  3. 3

    3-SAT∈Π2P3\text{-}\mathrm{SAT} \in \Pi_2^{\mathrm{P}}?

  4. 4

    Le risposte ai test di soddisfacibilità di knowledge base SHOIQ (OWL-2) ammettono disqualifiers succinti?

  5. 5

    CIRC SAT è riducibile a co-QSAT3\mathrm{co\text{-}QSAT}_3?

  6. 6

    Per ripristinare in ambito quantistico la complessità classica degli attacchi a forza bruta alla crittografia simmetrica, basta raddoppiare la lunghezza delle chiavi?

  7. 7

    Supponiamo EXP⊂NEXP\mathrm{EXP} \subset \mathrm{NEXP}. È vero che HAMILTON PATH non è Π2P\Pi_2^{\mathrm{P}}-completo?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT nondeterministica che controlla se una stringa è palindroma

Il metodo, passo per passo