Traccia E26

26 maggio 2026

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

0/7
  1. 1

    Nondet. spazio log⁡n\log n ⇒\Rightarrow det. spazio (log⁡n)2(\log n)^2?

  2. 2

    È vero che SCHÖNFINKEL-BERNAYS SAT non è NEXP-completo?

  3. 3

    Se P=NP\mathrm{P} = \mathrm{NP} sapremmo se esistono funzioni one-way?

  4. 4

    3-EXP=PH3\text{-}\mathrm{EXP} = \mathrm{PH}?

  5. 5

    Riduzione da co-QSAT3\mathrm{co\text{-}QSAT}_3 a MAX FLOW?

  6. 6

    Σ1P⊆2-EXP\Sigma_1^{\mathrm{P}} \subseteq 2\text{-}\mathrm{EXP}?

  7. 7

    Assumiamo PH=NEXP\mathrm{PH} = \mathrm{NEXP}. È vero che PRIMES non è NPSPACE-hard?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT con oracolo SAT che decide SAT-UNSAT

Il metodo, passo per passo