Traccia F03

31 maggio 2016, prova 03

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

0/7

1
$\mathrm{co\text{-}QSAT}_4$
2
$PRIMES è riducibile a TSP(D) ?$
3
$3\text{-}\mathrm{SAT} \in \Pi_2^{\mathrm{P}}$
4
$Le risposte ai test di soddisfacibilità di knowledge base SHOIQ (OWL-2) ammettono disqualifiers succinti?$
5
$\mathrm{co\text{-}QSAT}_3$
6
$Per ripristinare in ambito quantistico la complessità classica degli attacchi a forza bruta alla crittografia simmetrica, basta raddoppiare la lunghezza delle chiavi?$
7
$\mathrm{EXP} \subset \mathrm{NEXP}$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT nondeterministica che controlla se una stringa è palindroma

Il metodo, passo per passo

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

Input (una stringa di bit, per esempio 0110)

Nastro 1

▷101⊔⊔⊔⊔

Nastro 2

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

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

\sqcup

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$b$	$\sqcup$	$s$	$b, \rightarrow$	$b, \rightarrow$	scelta 1: copia $b$ , la prima metà continua
$s$	$b$	$\sqcup$	$m$	$b, \rightarrow$	$\sqcup, \leftarrow$	scelta 2: $b$ è il centro (lunghezza dispari), lo salta
$s$	$b$	$\sqcup$	$m$	$b, -$	$\sqcup, \leftarrow$	scelta 3: la prima metà finisce prima di $b$ (lunghezza pari)
$s$	$\sqcup$	$\sqcup$	$m$	$\sqcup, -$	$\sqcup, \leftarrow$	fine dell'input senza scelte: accetta solo la stringa vuota
$m$	$b$	$b$	$m$	$b, \rightarrow$	$b, \leftarrow$	cifre simmetriche uguali
$m$	$\sqcup$	$\triangleright$	$\text{yes}$	$\sqcup, -$	$\triangleright, \rightarrow$	finite insieme: palindroma

Eseguila passo per passo