Traccia GE23

20 gennaio 2023

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

0/7
  1. 1

    QSAT2\mathrm{QSAT}_2 è Σ2P\Sigma_2^{\mathrm{P}}-hard?

  2. 2

    I problemi in BQP richiedono, su un calcolatore tradizionale, spazio O(nk)O(n^k)?

  3. 3

    Supponiamo SCHÖNFINKEL-BERNAYS SAT ∈BPP\in \mathrm{BPP}. È vero che GEOGRAPHY non è riducibile a 2-SAT?

  4. 4

    È vero che PRIMES non è 4-EXP-hard?

  5. 5

    Riduzione da QSAT1\mathrm{QSAT}_1 a SAT-UNSAT?

  6. 6

    Problemi non risolubili in tempo n2n^2 ma in tempo (2n+1)6(2n+1)^6?

  7. 7

    EXACT TSP è Σ2P\Sigma_2^{\mathrm{P}}-hard?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che accetta le stringhe x;yx;y tali che xx e yy sono interi in binario della stessa lunghezza e x≤yx \le y (se non hanno la stessa lunghezza, rigetta)

Il metodo, passo per passo