Traccia G20v3

23 giugno 2020, versione 3

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

0/7

1
$\Pi_3^{\mathrm{P}}$
2
$\Sigma_2^{\mathrm{P}} \subseteq \Sigma_3^{\mathrm{P}}$
3
$\Sigma_1^{\mathrm{P}}$
4
$Dire se L e NL coincidono$
5
$Per ripristinare in ambito quantistico la complessità classica degli attacchi a forza bruta alla crittografia simmetrica, basta raddoppiare la lunghezza delle chiavi$
6
$O(2^n)$
7
$\mathrm{NL} \subseteq \mathrm{NP}$

Mancano 7 risposte.

Macchina di Turing

x;y

Il metodo, passo per passo

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

Input (due numeri binari separati da ;, per esempio 01;10)

Nastro 1

▷01;10⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

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

x \le y

Stato	letto₁ ( $y$ )	letto₂ ( $x$ )	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	copia $x$
$s$	$;$	$\sqcup$	$r$	$;, \rightarrow$	$\sqcup, \leftarrow$	testina 1 sulla prima cifra di $y$
$r$	$\sigma$	$b$	$r$	$\sigma, -$	$b, \leftarrow$	riavvolge il 2° nastro
$r$	$\sigma$	$\triangleright$	$e$	$\sigma, -$	$\triangleright, \rightarrow$	pronto a confrontare
$e$	$b$	$b$	$e$	$b, \rightarrow$	$b, \rightarrow$	cifre uguali
$e$	$1$	$0$	$l$	$1, \rightarrow$	$0, \rightarrow$	$x$ minore di $y$
$e$	$0$	$1$	$\text{no}$	$0, -$	$1, -$	$x$ maggiore di $y$
$l$	$b$	$b'$	$l$	$b, \rightarrow$	$b', \rightarrow$	ormai conta solo la lunghezza ( $b'$ è un altro bit qualsiasi)
$e$ o $l$	$\sqcup$	$\sqcup$	$\text{yes}$	$\sqcup, -$	$\sqcup, -$	stessa lunghezza e $x \le y$
$e$ o $l$	$b$	$\sqcup$	$\text{no}$	—	—	$y$ più lungo
$e$ o $l$	$\sqcup$	$b$	$\text{no}$	—	—	$x$ più lungo

Eseguila passo per passo