Traccia ND

senza data (foto nella Raccolta)

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

0/7
  1. 1

    È vero che 2-COL non può essere deciso da una MdT nondeterministica in spazio polinomiale?

  2. 2

    I problemi risolubili in tempo polinomiale con un algoritmo quantistico a errore limitato richiedono, su un calcolatore tradizionale, spazio O(2n)O(2^n)?

  3. 3

    Esistono problemi non risolubili in tempo n3n^3 ma risolubili in tempo (2n+1)9(2n+1)^9? (con MdT deterministiche)

  4. 4

    Dire se 3-COL appartiene a Σ2P\Sigma_2^{\mathrm{P}}

  5. 5

    Dire se Σ1P⊂3-EXP\Sigma_1^{\mathrm{P}} \subset 3\text{-}\mathrm{EXP}

  6. 6

    Dire se CLIQUE è PH-hard

  7. 7

    Assumiamo che NL e BPP coincidano. Dire se co-QSAT1\mathrm{co\text{-}QSAT}_1 è BPP-hard

Mancano 7 risposte.
8
Macchina di Turing

Programmare una MdT con oracolo SAT che decide SAT-UNSAT

Il metodo, passo per passo