Esiste · per ogni · esiste

La gerarchia polinomiale, un piano alla volta

Parti da NP: «esiste una soluzione verificabile». Ogni nuovo livello aggiunge un'alternanza tra «esiste» e «per ogni».

1. Aggiungi un’alternanza

Parte da «esiste»

\exists

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

Partendo da $\forall$ : $\htmlData{term=coNP}{\mathrm{coNP}}$

Esiste un assegnamento che rende vera la formula?

Un solo blocco esistenziale: basta trovare un certificato. Cambiando $\exists$ in $\forall$ ottieni la famiglia complementare.

Esempio:

\mathrm{SAT}

Conta i blocchi alternati, non le variabili. $\exists x\ \exists y$ è un solo blocco. PH raccoglie tutti i livelli finiti; $\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}$ .

2. Prova con i quantificatori

Scegli un esercizio: prima costruisci il prefisso, poi valuta una formula.

Costruisci un prefisso e trova il livello

\exists y_1\ \forall y_2\ R(x, y_1, y_2)

2 blocchi alternati, il primo è $\exists$ : la classe è $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ . Una macchina che lo decide: nondeterministica polinomiale con oracolo $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ .

$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ è completo per questa classe.

Valuta una QBF:

\exists

è OR,

\forall

è AND

Prova a prevederlo: la formula è vera o falsa?

Prefisso con 2 blocchi, il primo $\exists$ : è un'istanza di $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ , che sta in $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ .

3. Collega i livelli

Che cosa significa

\Delta

? E dove sta DP?

$\Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}^{\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}}$ : tempo polinomiale deterministico con un oracolo $\Sigma$ del piano sotto. Al piano 1 $\htmlData{term=Δ1}{\Delta_1^{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}$ ; al piano 2 $\htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} = \htmlData{term=P}{\mathrm{P}}^{\htmlData{term=NP}{\mathrm{NP}}}$ . Non ha quantificatori suoi: sta tra due piani.

\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} \cup \Pi_i^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}} \cap \Pi_{i+1}^{\htmlData{term=P}{\mathrm{P}}}

$\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ : una domanda all'oracolo, e si copia la risposta.
$\Pi_i^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ : una domanda sul complemento, e si inverte la risposta.
$\Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}^{\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}}$ : stesso oracolo; una macchina deterministica è una nondeterministica che non usa le scelte.
$\Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Pi_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ : $\Delta$ è chiusa per complemento, quindi se $L \in \Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ anche $\mathrm{co}\text{-}L \in \Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}}$ .

DP sta sotto $\htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}}$ : bastano due domande all'oracolo, una per la parte NP e una per la parte coNP. Non è un piano autonomo della gerarchia.

\htmlData{term=NP}{\mathrm{NP}} \cup \htmlData{term=coNP}{\mathrm{coNP}} \subseteq \htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \cap \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}

Esempio (F07): SAT-UNSAT si riduce a $\mathrm{co\text{-}QSAT}_3$ ? SÌ: $\htmlData{term=problem:SATUNSAT}{\mathrm{SAT\text{-}UNSAT}} \in \htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} \subseteq \htmlData{term=Δ3}{\Delta_3^{\mathrm{P}}} \subseteq \htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ , e $\mathrm{co\text{-}QSAT}_3$ è $\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}$ -completo.

La scheda sintetica di DP

Torre completa e ipotesi di collasso

Ipotesi

Nessuna di queste uguaglianze è dimostrata, e nessuna inclusione della torre è dimostrata stretta. Scegli un'ipotesi per vedere fin dove crollerebbe la torre.

inclusione dimostrata (dal basso verso l'alto), non si sa se stretta

=?non si sa se

\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}

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

Piano 2, lato

\exists

(

\Sigma

)

Scheda della classe

Intuizione

La risposta sì si descrive con 2 blocchi di quantificatori alternati che cominciano con esiste: «esiste una scelta tale che, per ogni contromossa, il controllo passa».

Definizione con gli oracoli

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

Macchina nondeterministica polinomiale che può fare domande a un oracolo per un problema di $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ (basta un problema completo, per esempio $\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1$ ).

Definizione con i quantificatori

L \in \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \iff L = \{\, x : \exists y_1\ \forall y_2\ (x, y_1, y_2) \in R \,\}

$R$ si decide in tempo polinomiale ed è bilanciata (ogni $y$ lungo al più $|x|^k$ ). È il Corollario 2 del Teorema 17.8 (dispensa cap. 17): ogni oracolo vale un blocco di quantificatori in più.

Esempio

\exists p\ \forall q.\ p \lor q

È vera: si sceglie $p$ vera, e allora $p \lor q$ è vera per ogni $q$ .

Come la decide una macchina $\htmlData{term=NP}{\mathrm{NP}}^{\htmlData{term=NP}{\mathrm{NP}}}$ . Indovina $p$ , poi chiede all'oracolo SAT: «esiste un $q$ che rende falsa la formula?», cioè « $\neg(p \lor q)$ è soddisfacibile?». Sul ramo con $p$ vera la risposta è no, e il ramo accetta. Sul ramo con $p$ falsa resta $\neg q$ , soddisfacibile, e il ramo rifiuta. Basta un ramo che accetta: la risposta è sì.

Problemi completi

$\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2$ , CIRC SAT, STRATEGIC COMPANIES.

Uguale a $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ?

Non si sa. Se $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ , PH collasserebbe al piano 2 (Teorema 17.9). Prova l'ipotesi nel menu sopra la torre.

Dove sta nella torre

Contiene

\htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}}

, DP, NP, coNP, P

È contenuta in

\htmlData{term=Δ3}{\Delta_3^{\mathrm{P}}}

\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}

\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}

\htmlData{term=Δ4}{\Delta_4^{\mathrm{P}}}

\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}

\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}

, PH, PSPACE

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

Fonti: dispensa cap. 16–17; slide Lez. 9.

Come riconoscere un collasso

Se $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ per un $i \ge 1$ , allora $\htmlData{term=PH}{\mathrm{PH}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}$ : i livelli superiori non aggiungono potenza (Teorema 17.9).

$\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}} \Rightarrow \htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=P}{\mathrm{P}}$

Il controllo deterministico basta per tutti i livelli.

$\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}} \Rightarrow \htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}}$

Collassa al primo livello; non implica da solo $\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}$ .

Se un problema completo per un livello superiore entra in un livello inferiore, scrivi prima l'inclusione che ne segue. Poi cerca l'uguaglianza $\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}$ .

Cerca i teoremi sul collasso

Riduzioni tra problemi dei livelli

Da (problema A)A (problema B)

Gli esercizi della dispensa (cap. 17.2.1):

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

→

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

altro

Non si sa; esisterebbe solo se PH collassa al piano 2: $\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}$ contiene sia $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ sia $\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ (perché $\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} \supseteq \htmlData{term=Δ3}{\Delta_3^{\mathrm{P}}} \supseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \cup \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ ); se fosse $\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ , anche l'altro lato del piano 2 starebbe in $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}$ , quindi $\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}$ (Teorema 17.9).

Regola usata: se A è completo per X e B per Y, A si riduce a B esattamente quando $X \subseteq Y$ , perché le classi sono chiuse per riduzioni.

Fonti: dispensa cap. 16–17; slide Lez. 9.