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

inclusione dimostrata, uguaglianza aperta

P è contenuta in NP. Non sappiamo se le due classi siano uguali.

Una precisazione su questa coppia

\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}

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

è la domanda aperta più famosa. Se fosse vera:

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

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

\htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=NEXP}{\mathrm{NEXP}}

Perché: le risposte da dare all'esame

\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}

SÌ

\subseteq

NP ∩ coNP

\subseteq

Se sia stretta non si sa.

Perché ogni passo

$\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=NP}{\mathrm{NP}}$ : per definizione di intersezione

\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=P}{\mathrm{P}}

altro: solo se

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

Si sa che

\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}

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

Ne seguirebbe:

$\htmlData{term=P}{\mathrm{P}} = \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=EXP}{\mathrm{EXP}} = \htmlData{term=NEXP}{\mathrm{NEXP}}$

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

: PH collasserebbe al piano 0 (

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

) ed

\htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=NEXP}{\mathrm{NEXP}}

per il padding.

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

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	P	NP
Che cos'è	Tempo polinomiale deterministico	Tempo polinomiale nondeterministico
Forma della risposta sì	$\htmlData{term=P}{\mathrm{P}} = \Sigma_0^{\mathrm{P}} = \htmlData{term=Δ1}{\Delta_1^{\mathrm{P}}}$ : nessun quantificatore, solo un controllo polinomiale	$\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ : $\exists y\, R(x,y)$
Chiusa per complemento	sì (classe deterministica)	non si sa ( $\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}$ è aperto)
Problemi completi	MAX FLOW è P-completo (dispensa cap. 22). CIRCUIT VALUE e HORNSAT P-completi stanno negli appunti Lez. 7 §8 e Lez. 8 ✱ solo appunti. $\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=P}{\mathrm{P}}$ (dispensa cap. 22), ma non è noto se sia P-completo.	$\htmlData{term=problem:SAT}{\mathrm{SAT}} = \htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ (Cook-Levin), 3-SAT, CLIQUE, INDEPENDENT SET, NODE COVER, HAMILTON PATH, TSP(D), 3-COLORING, KNAPSACK e gli altri della Lez. 8.
Fonti	dispensa cap. 5, 7, 22; slide Lez. 4–5; appunti Lez. 1, 7, 8	dispensa cap. 3, 5, 12–13, 22; appunti Lez. 3, 7, 8