Le risorse del calcolo

Classi di complessità

Separazioni dimostrate Questioni aperte

inclusione dimostrata, non si sa se stretta

inclusione stretta dimostrata

separazione dimostrata tra classi lontane

non si sa nemmeno se una contiene l'altra

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

Secondo piano di PH, lato

\exists

(

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

)

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

chiusa per complemento: non si sa (il complemento è

\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}

)

Confronta con…

"Esiste una scelta tale che, per ogni contromossa, il controllo passa": un certificato che deve resistere a tutti i controesempi. La macchina NP indovina il certificato, l'oracolo NP verifica che non esistano controesempi.

Vedi $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ nei piani di PH →

Dove sta: inclusioni e questioni aperte

È contenuta in

\subseteq

Σ_i^P

\subseteq

Π_i^P

\subseteq

\subseteq

PSPACE

\subseteq

EXP

\subseteq

NEXP

\subsetneq

\subsetneq

\subsetneq

coRE

Contiene

\supseteq

\supseteq

\supseteq

\supseteq

NP ∩ coNP

\supseteq

\supseteq

coNP

\supseteq

\supseteq

Δ₂^P

Rapporto non noto

?

Π₂^P

$\subsetneq$ in rosso: inclusione stretta dimostrata (anche quando segue dal fatto che l'inclusione opposta è esclusa). $\subseteq$ senza colore: dimostrata, non si sa se stretta. ? : non si sa nemmeno se una contenga l'altra. $\neq$ : diverse, ma nessuna contiene l'altra.

Problemi completi

$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ , CIRC SAT (circoscrizione) e STRATEGIC COMPANIES sono $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ -completi.

Problemi: STRATEGIC COMPANIES · CIRC SAT · $\mathrm{QSAT}_i$ (con $i = 2$ )

Teoremi su $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$

Proposizione $C^D = C^{\mathrm{co}D}$ · Teorema (CIRC SAT e CIRC VALIDITY) · STRATEGIC COMPANIES è $\Sigma_2^{\mathrm{P}}$ -completo

Dalle tracce d'esame

2\text{-}\mathrm{EXP} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

? (F07)

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 2\text{-}\mathrm{EXP}

\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-hard? (GE23)

SÌ

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-completo

EXACT TSP è

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-hard? (GE23)

altro: solo se

\htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

EXACT TSP è DP-completo e

\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

;

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-hard darebbe

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=DP}{\mathrm{DP}}

Supponiamo VALIDITY riducibile a TSP(D). È vero che EXACT TSP non è

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-completo? (F14)

VALIDITY coNP-completo

\le \htmlData{term=problem:TSPD}{\mathrm{TSP(D)}} \in \htmlData{term=NP}{\mathrm{NP}} \Rightarrow \htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}} \Rightarrow \htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}}

; allora

\htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

e il DP-completo EXACT TSP è

\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}

-completo

Fonti: dispensa cap. 17; slide Lez. 9; appunti Lez. 9 §3–§5