Traccia F08

31 maggio 2016, prova 08

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

0/7
  1. 1

    PSPACE≠4-EXP\mathrm{PSPACE} \neq 4\text{-}\mathrm{EXP}?

  2. 2

    Esistono problemi risolubili nondeterministicamente in spazio 2log⁡n2 \log n ma non deterministicamente in spazio (2log⁡n)2(2 \log n)^2?

  3. 3

    Supponiamo che esista una riduzione da SCHÖNFINKEL-BERNAYS SAT a QSAT3\mathrm{QSAT}_3. coNP⊆L\mathrm{coNP} \subseteq \mathrm{L}?

  4. 4

    PSPACE non è strettamente contenuto in Π2P\Pi_2^{\mathrm{P}}?

  5. 5

    co-QSAT3∈Π3P\mathrm{co\text{-}QSAT}_3 \in \Pi_3^{\mathrm{P}}?

  6. 6

    L∈PPL \in \mathrm{PP}: è noto un metodo per ridurre la probabilità di errore sotto una soglia prefissata in tempo polinomiale?

  7. 7

    TSP(D) è NL-completo?

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT con oracolo SAT che decide SAT-UNSAT

Il metodo, passo per passo