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=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}} \subsetneq \htmlData{term=R}{\mathrm{R}}

inclusione stretta dimostrata

$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ è contenuta in R, e le due classi sono diverse.

Perché: le risposte da dare all'esame

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

Se fosse $\htmlData{term=R}{\mathrm{R}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ , si avrebbe:

NEXP

\subsetneq

\overset{?}{\subseteq}

NP ∩ coNP

\subseteq

cioè $\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ , contro $\htmlData{term=NP}{\mathrm{NP}} \subsetneq \htmlData{term=NEXP}{\mathrm{NEXP}}$ (gerarchia nondeterministica: $\htmlData{term=NP}{\mathrm{NP}} \subseteq \mathrm{NTIME}(2^n) \subsetneq \mathrm{NTIME}(2^{n^2}) \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}}$ ; appunti Lez. 5 §7 e Lez. 10 §4 ✱: la dispensa (cap. 8) e le slide danno la gerarchia nondeterministica solo tra polinomi, $\mathrm{NTIME}(n^c) \subsetneq \mathrm{NTIME}(n^d)$ ; il passo $\mathrm{NTIME}(2^n) \subsetneq \mathrm{NTIME}(2^{n^2})$ viene dagli appunti).

Perché ogni passo

$\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=R}{\mathrm{R}}$ : una macchina con un budget di tempo si ferma sempre, quindi decide il suo linguaggio (appunti Lez. 10 §4 («ogni k-EXP sta in R»))
$\htmlData{term=R}{\mathrm{R}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ : ipotesi: $\htmlData{term=R}{\mathrm{R}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$
$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ : per definizione di intersezione

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

SÌ

NP ∩ coNP

\subseteq

\subseteq

\subseteq

Δ₂^P

\subseteq

Σ₂^P

\subseteq

Σ_i^P

\subseteq

\subseteq

PSPACE

\subseteq

EXP

\subseteq

NEXP

\subsetneq

Stretta perché $\htmlData{term=NP}{\mathrm{NP}} \subsetneq \htmlData{term=NEXP}{\mathrm{NEXP}}$ (gerarchia nondeterministica: $\htmlData{term=NP}{\mathrm{NP}} \subseteq \mathrm{NTIME}(2^n) \subsetneq \mathrm{NTIME}(2^{n^2}) \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}}$ ).

Perché ogni passo

$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ : per definizione di intersezione
$\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=DP}{\mathrm{DP}}$ : si prende $L_2 = \Sigma^*$ (tutte le stringhe), che sta in coNP (appunti Lez. 9 §1)
$\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}}$ : bastano due domande all'oracolo NP: $x \in L_1$ ? e $x \in L_2$ ? (dispensa cap. 16: «Obviously $\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ »)
$\htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ : una macchina deterministica è un caso particolare di nondeterministica (dispensa cap. 17; appunti Lez. 9 §3)
$\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ : ogni piano contiene i piani precedenti (dispensa cap. 17)
$\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} \subseteq \htmlData{term=PH}{\mathrm{PH}}$ : PH è l'unione di tutti i piani (dispensa cap. 17)
$\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ : ogni piano si decide in spazio polinomiale (dispensa cap. 17.1, Proposizione « $\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ »)
$\htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}}$ : $\mathrm{SPACE}(f) \subseteq \mathrm{TIME}(k^f)$ : si contano le configurazioni (dispensa cap. 10; slide Lez. 5)
$\htmlData{term=EXP}{\mathrm{EXP}} \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}}$ : $\text{deterministico} \subseteq \text{nondeterministico}$ (appunti Lez. 10 §4)
$\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=R}{\mathrm{R}}$ : una macchina con un budget di tempo si ferma sempre, quindi decide il suo linguaggio (appunti Lez. 10 §4 («ogni k-EXP sta in R»))

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

un'inclusione tra le due è esclusa, quindi non possono essere uguali.

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	R	NP ∩ coNP
Che cos'è	Linguaggi ricorsivi (decidibili)	$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ : problemi con una prova corta in entrambi i versi
Forma della risposta sì	macchina che si ferma sempre	sia $\exists y\, R(x,y)$ sia $\forall y\, R'(x,y)$ , con due relazioni diverse
Chiusa per complemento	sì	sì (l'intersezione di una classe con la sua co-classe)
Problemi completi	Non si parla di completezza in R nel corso.	Non se ne conoscono: $\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ non è una classe "sintattica" come DP.
Fonti	dispensa cap. 1.5, 22; appunti Lez. 10 §4, §7	dispensa cap. 14; appunti Lez. 4 §7, Lez. 8 §8, Lez. 9 §1