Collega i concetti

Confronta due classi

Una classe contiene l'altra? Sono diverse? Scegli una coppia per vedere che cosa sappiamo e che cosa resta aperto.

\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}

inclusione dimostrata, uguaglianza aperta

NL è contenuta in $\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ . Non sappiamo se le due classi siano uguali.

Perché: le risposte da dare all'esame

\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}

SÌ

\subseteq

\subseteq

NP ∩ coNP

Se sia stretta non si sa.

Perché ogni passo

$\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=P}{\mathrm{P}}$ : $\mathrm{NSPACE}(\log n) \subseteq \mathrm{TIME}(k^{\log n + \log n})$ : reachability method sul grafo delle configurazioni, che ha un numero polinomiale di nodi (Teorema 7.4(c), dispensa cap. 11; slide Lez. 5)
$\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ : $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ e P è chiusa per complemento, quindi $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=coNP}{\mathrm{coNP}}$ (dispensa cap. 14, Proposizione)

\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}} \subseteq \htmlData{term=NL}{\mathrm{NL}}

altro: solo se

\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=NL}{\mathrm{NL}}

Si sa che

\htmlData{term=NL}{\mathrm{NL}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}

: l'inclusione richiesta varrebbe solo se le due classi fossero uguali, e non si sa.

Ne seguirebbe:

$\htmlData{term=NL}{\mathrm{NL}} = \htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$

\htmlData{term=NL}{\mathrm{NL}} = \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}

altro: non si sa

nessuna delle due inclusioni mancanti è dimostrata o esclusa.

Le risposte sono calcolate dalle inclusioni e dalle separazioni della mappa, con le regole del corso: passaggio ai complementi, $\htmlData{term=R}{\mathrm{R}} = \htmlData{term=RE}{\mathrm{RE}} \cap \htmlData{term=coRE}{\mathrm{coRE}}$ , collasso di PH (Teorema 17.9), padding (Teorema 20.1). "Solo se" vuol dire che la risposta dipende da una questione aperta.

Definizioni e problemi delle due classi

Aspetto	NL	NP ∩ coNP
Che cos'è	Spazio logaritmico nondeterministico	$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ : problemi con una prova corta in entrambi i versi
Forma della risposta sì	un run che accetta, con memoria $\log n$	sia $\exists y\, R(x,y)$ sia $\forall y\, R'(x,y)$ , con due relazioni diverse
Chiusa per complemento	sì: $\htmlData{term=NL}{\mathrm{NL}} = \mathrm{coNL}$	sì (l'intersezione di una classe con la sua co-classe)
Problemi completi	REACHABILITY e 2-SAT sono NL-completi (appunti Lez. 8 §3; Lez. 10 §8). ✱ solo appunti La dispensa dà solo $\htmlData{term=problem:REACH}{\mathrm{REACHABILITY}} \in \htmlData{term=NL}{\mathrm{NL}}$ e, per Savitch, $\in \mathrm{SPACE}(\log^2 n)$ .	Non se ne conoscono: $\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ non è una classe "sintattica" come DP.
Fonti	dispensa cap. 5 e 11; slide Lez. 4–5; appunti Lez. 3, 5 §10, 8 §3	dispensa cap. 14; appunti Lez. 4 §7, Lez. 8 §8, Lez. 9 §1