Traccia F08

31 maggio 2016, prova 08

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

0/7

1
$\mathrm{PSPACE} \neq 4\text{-}\mathrm{EXP}$
2
$2 \log n$
3
$\mathrm{QSAT}_3$
4
$\Pi_2^{\mathrm{P}}$
5
$\mathrm{co\text{-}QSAT}_3 \in \Pi_3^{\mathrm{P}}$
6
$L \in \mathrm{PP}$
7
$TSP(D) è NL - completo ?$

Mancano 7 risposte.

Macchina di Turing

Programmare una MdT con oracolo SAT che decide SAT-UNSAT

Il metodo, passo per passo

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

Input (due formule separate da ;, con variabili e i connettivi ! & | e le parentesi: per esempio (x|y)&!x;x&!x)

Nastro 1

▷(x|y)&!x;x&!x⊔⊔

Nastro 2 (query)

▷⊔⊔⊔⊔⊔⊔⊔

Stato sPasso 0

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

x

Stato	letto₁	letto₂	nuovo stato	scritto₁, mossa₁	scritto₂, mossa₂	note
$s$	$\triangleright$	$\triangleright$	$s$	$\triangleright, \rightarrow$	$\triangleright, \rightarrow$
$s$	$\sigma$	$\sqcup$	$s$	$\sigma, \rightarrow$	$\sigma, \rightarrow$	copia $x$
$s$	$;$	$\sqcup$	$q_?$	$;, -$	$\sqcup, -$	" $x \in \mathrm{SAT}$ ?"
$q_{\text{NO}}$	$;$	$\sqcup$	$\text{no}$	$;, -$	$\sqcup, -$	$x$ insoddisfacibile
$q_{\text{YES}}$	$;$	$\sqcup$	$r$	$;, -$	$\sqcup, \leftarrow$	$x$ soddisfacibile: si passa a $y$
$r$	$;$	$\sigma$	$r$	$;, -$	$\sqcup, \leftarrow$	cancella la query
$r$	$;$	$\triangleright$	$a$	$;, \rightarrow$	$\triangleright, \rightarrow$	query cancellata
$a$	$\sigma$	$\sqcup$	$a$	$\sigma, \rightarrow$	$\sigma, \rightarrow$	copia $y$
$a$	$\sqcup$	$\sqcup$	$q_?$	$\sqcup, -$	$\sqcup, -$	" $y \in \mathrm{SAT}$ ?"
$q_{\text{YES}}$	$\sqcup$	$\sqcup$	$\text{no}$	$\sqcup, -$	$\sqcup, -$	$y$ soddisfacibile
$q_{\text{NO}}$	$\sqcup$	$\sqcup$	$\text{yes}$	$\sqcup, -$	$\sqcup, -$	$x$ sì, $y$ no

Eseguila passo per passo