Traccia SP

Domande sparse e MdT senza traccia (SP)

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

0/5

a
$Sia L un problema in PP . È noto un metodo per ridurre la probabilità di errore sotto una soglia prefissata in tempo polinomiale?$
b
$f(n)$
c
$Esistono linguaggi che sono accettati da MdT nondeterministiche ma non sono in RE ?$
d
$O(2^{n/2})$
e
$n$

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

#	Stato	Legge₁	Legge₂		Nuovo stato	Scrive₁	Mossa₁	Scrive₂	Mossa₂	Commento
1

Input (matrice di adiacenza ("," tra gli elementi, ";" tra le righe), poi ":" e K in binario: per esempio 0,1,0;1,0,1;0,1,0:10)

Nastro 1

▷0,1,0;1,0,1;0,1,0:10⊔⊔

Nastro 2 (query)

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

Prossima transizione (riga 1): δ(s, ▷, ▷) = (s, ▷, →, ▷, →) · supera l'inizio dei due nastri

K

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$0$	$\sqcup$	$s$	$0, \rightarrow$	$1, \rightarrow$	inverte il bit: c'è un arco in $\bar G$
$s$	$1$	$\sqcup$	$s$	$1, \rightarrow$	$0, \rightarrow$	inverte il bit: niente arco in $\bar G$
$s$	$,$	$\sqcup$	$s$	$,, \rightarrow$	$,, \rightarrow$	copia il separatore
$s$	$;$	$\sqcup$	$s$	$;, \rightarrow$	$;, \rightarrow$	copia il separatore
$s$	$:$	$\sqcup$	$k$	$:, \rightarrow$	$:, \rightarrow$	fine della matrice
$k$	$b$	$\sqcup$	$k$	$b, \rightarrow$	$b, \rightarrow$	copia $K$ senza cambiarlo
$k$	$\sqcup$	$\sqcup$	$q_?$	$\sqcup, -$	$\sqcup, -$	" $\bar G$ ha una cricca di almeno $K$ nodi?"
$q_{\text{YES}}$	$\sqcup$	$\sqcup$	$\text{yes}$	$\sqcup, -$	$\sqcup, -$	c'è un independent set di almeno $K$ nodi
$q_{\text{NO}}$	$\sqcup$	$\sqcup$	$\text{no}$	$\sqcup, -$	$\sqcup, -$	non c'è

Eseguila passo per passo