Traccia LU22

22 luglio 2022

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

0/7
  1. 1

    Dire se VALIDITY è riducibile a co-QSAT4\mathrm{co\text{-}QSAT}_4

  2. 2

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

  3. 3

    Se L1L_1 è riducibile a L2L_2 e L2L_2 è riducibile a L3L_3, allora L1L_1 è riducibile a L3L_3

  4. 4

    È falso che NPSPACE⊆4-EXP\mathrm{NPSPACE} \subseteq 4\text{-}\mathrm{EXP}?

  5. 5

    Supponiamo che L⊂Π4P\mathrm{L} \subset \Pi_4^{\mathrm{P}}. Dire se PSPACE⊆L\mathrm{PSPACE} \subseteq \mathrm{L}

  6. 6

    Dire se P⊆BQP\mathrm{P} \subseteq \mathrm{BQP}

  7. 7

    Dire se Σ2P⊆coNP\Sigma_2^{\mathrm{P}} \subseteq \mathrm{coNP}

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT che, data la stringa binaria x;yx;y, effettua la somma binaria tra xx e yy e rigetta nel caso di stringhe di lunghezza diversa o di overflow

Il metodo, passo per passo