Traccia SP

Domande sparse e MdT senza traccia (SP)

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

0/5
  1. a

    Sia L un problema in PP. È noto un metodo per ridurre la probabilità di errore sotto una soglia prefissata in tempo polinomiale?

  2. b

    Un problema risolubile con 1 nastro in tempo f(n)f(n) non può essere risolto in tempo f(n)2f(n)^2 con 1 nastro solo?

  3. c

    Esistono linguaggi che sono accettati da MdT nondeterministiche ma non sono in RE?

  4. d

    Dire se HAMILTON PATH può essere risolto in tempo O(2n/2)O(2^{n/2}) con un algoritmo quantistico

  5. e

    Esistono problemi risolubili nondeterministicamente in spazio nn che non sono risolubili deterministicamente in tempo k2nk^{2n}?

Mancano 5 risposte.
MdT
Macchina di Turing

Programmare una MdT con oracolo che decide se un grafo ha un independent set di almeno K nodi, usando un oracolo per CLIQUE

Il metodo, passo per passo