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}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}

inclusione dimostrata, uguaglianza aperta

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

Perché: le risposte da dare all'esame

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

altro: solo se

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

Si sa che

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

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

Ne seguirebbe:

$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}$

\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}

: per il Teorema 17.11 PH collasserebbe a un livello finito.

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

: PH collasserebbe al primo livello (

\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}}

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

SÌ

NP ∩ coNP

\subseteq

\subseteq

\subseteq

Δ₂^P

\subseteq

Σ₂^P

\subseteq

Σ_i^P

\subseteq

\subseteq

PSPACE

Se sia stretta non si sa.

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}} = \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	PSPACE	NP ∩ coNP
Che cos'è	Spazio polinomiale ( $= \mathrm{NPSPACE}$ )	$\htmlData{term=NP}{\mathrm{NP}} \cap \htmlData{term=coNP}{\mathrm{coNP}}$ : problemi con una prova corta in entrambi i versi
Forma della risposta sì	alternanze in numero qualsiasi (QSAT)	sia $\exists y\, R(x,y)$ sia $\forall y\, R'(x,y)$ , con due relazioni diverse
Chiusa per complemento	sì (classe deterministica)	sì (l'intersezione di una classe con la sua co-classe)
Problemi completi	QSAT, GEOGRAPHY e GO sono PSPACE-completi; anche la combined complexity delle query (dispensa cap. 18–19).	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, 10, 11.1, 17–19; slide Lez. 5, 9; appunti Lez. 5 §10, Lez. 9 §6–§7	dispensa cap. 14; appunti Lez. 4 §7, Lez. 8 §8, Lez. 9 §1