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

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

Partendo da ∀\forall: coNP\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: SAT\mathrm{SAT} →

Conta i blocchi alternati, non le variabili. ∃x ∃y\exists x\ \exists y è un solo blocco. PH raccoglie tutti i livelli finiti; PH⊆PSPACE\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
∃y1 ∀y2 R(x,y1,y2)\exists y_1\ \forall y_2\ R(x, y_1, y_2)

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

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

Valuta una QBF: ∃\exists è OR, ∀\forall è AND
p = Vp = Fq = Vq = Fq = Vq = F∃pOR∀qANDφ = ?φ = ?∀qANDφ = ?φ = ?

Prova a prevederlo: la formula è vera o falsa?

Prefisso con 2 blocchi, il primo ∃\exists: è un'istanza di QSAT2\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2, che sta in Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}. Formula da: appunti Lez. 9 §3.

3. Collega i livelli

Che cosa significa Δ\Delta? E dove sta DP?

Δi+1P=PΣiP\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 Δ1P=PP=P\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 Δ2P=PNP\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.

ΣiP∪ΠiP⊆Δi+1P⊆Σi+1P∩Πi+1P\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}}}
  • ΣiP⊆Δi+1P\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.
  • ΠiP⊆Δi+1P\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.
  • Δi+1P⊆Σi+1P=NPΣiP\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.
  • Δi+1P⊆Πi+1P\Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}} \subseteq \Pi_{i+1}^{\htmlData{term=P}{\mathrm{P}}}: Δ\Delta è chiusa per complemento, quindi se L∈Δi+1PL \in \Delta_{i+1}^{\htmlData{term=P}{\mathrm{P}}} anche co-L∈Σi+1P\mathrm{co}\text{-}L \in \Sigma_{i+1}^{\htmlData{term=P}{\mathrm{P}}}.

DP sta sotto Δ2P\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.

NP∪coNP⊆DP⊆Δ2P⊆Σ2P∩Π2P\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 co-QSAT3\mathrm{co\text{-}QSAT}_3? SÌ: SAT-UNSAT∈DP⊆Δ2P⊆Π2P⊆Δ3P⊆Π3P\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 co-QSAT3\mathrm{co\text{-}QSAT}_3 è Π3P\htmlData{term=Π3}{\Pi_3^{\mathrm{P}}}-completo.

La scheda sintetica di DP →
Torre completa e ipotesi di collasso

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

piano 0piano 1piano 2piano 3piano 4⋮⋮?=?=?=?=?PΔ₀ᴾ = Σ₀ᴾ = Π₀ᴾNPΣ₁ᴾcoNPΠ₁ᴾDPtra piano 1 e 2Δ2PPNPΣ2PNPNPΠ2PcoNPNPΔ3PPΣ₂ᴾΣ3PNPΣ₂ᴾΠ3PcoNPΣ₂ᴾΔ4PPΣ₃ᴾΣ4PNPΣ₃ᴾΠ4PcoNPΣ₃ᴾPHunione dei pianiPSPACEQSAT completo
inclusione dimostrata (dal basso verso l'alto), non si sa se stretta
=?non si sa se ΣiP=ΠiP\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}
Come riconoscere un collasso

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

P=NP⇒PH=P\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.

NP=coNP⇒PH=NP\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 P=NP\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 ΣiP=ΠiP\Sigma_i^{\htmlData{term=P}{\mathrm{P}}} = \Pi_i^{\htmlData{term=P}{\mathrm{P}}}.

Cerca i teoremi sul collasso →
Riduzioni tra problemi dei livelli
→

Gli esercizi della dispensa (cap. 17.2.1):

QSAT4\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_4 → QSAT2\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2altro

Non si sa; esisterebbe solo se PH collassa al piano 2: Σ4P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} contiene sia Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} sia Π2P\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} (perché Σ4P⊇Δ3P⊇Σ2P∪Π2P\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 Σ4P⊆Σ2P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}, anche l'altro lato del piano 2 starebbe in Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}, quindi Σ2P=Π2P\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⊆YX \subseteq Y, perché le classi sono chiuse per riduzioni.

Verifica nelle tracce: 26 domande su PH
Σ4P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} non è strettamente contenuto in 3-EXP? (F06)
NO
Σ4P⊆PH⊆PSPACE⊆EXP⊊2-EXP⊊3-EXP\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} \subseteq \htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 2\text{-}\mathrm{EXP} \subsetneq 3\text{-}\mathrm{EXP}: è strettamente contenuto
2-EXP⊆Σ2P2\text{-}\mathrm{EXP} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}? (F07)
NO
Σ2P⊆PSPACE⊆EXP⊊2-EXP\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 2\text{-}\mathrm{EXP}
3-EXP=PH3\text{-}\mathrm{EXP} = \htmlData{term=PH}{\mathrm{PH}}? (E26)
NO
PH⊆PSPACE⊆EXP⊊3-EXP\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} \subsetneq 3\text{-}\mathrm{EXP}
Σ4P⊂Σ3P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} \subset \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}? (G16)
NO
Σ3P⊆Σ4P\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \subseteq \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}, il contenimento stretto opposto è impossibile
È falso che Σ3P⊆Π4P\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \subseteq \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}? (G16)
NO
Σ3P⊆Δ4P⊆Π4P\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \subseteq \htmlData{term=Δ4}{\Delta_4^{\mathrm{P}}} \subseteq \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}
È falso che P⊆PH\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=PH}{\mathrm{PH}}? (L18)
NO
P=Σ0P⊆PH\htmlData{term=P}{\mathrm{P}} = \Sigma_0^{\mathrm{P}} \subseteq \htmlData{term=PH}{\mathrm{PH}}
Π4P⊆L\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}} \subseteq \htmlData{term=L}{\mathrm{L}}? (L18)
altro: solo se Π4P=L\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}} = \htmlData{term=L}{\mathrm{L}}
L⊆P⊆Π4P\htmlData{term=L}{\mathrm{L}} \subseteq \htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}; il contrario farebbe collassare L=NL=P=PH\htmlData{term=L}{\mathrm{L}} = \htmlData{term=NL}{\mathrm{NL}} = \htmlData{term=P}{\mathrm{P}} = \htmlData{term=PH}{\mathrm{PH}}, questione aperta
QSAT∈Π2P\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}? (F07)
altro: solo se PSPACE=Π2P\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}
QSAT PSPACE-completo; collasso di PH al livello 2
È vero che QSAT1\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1 non appartiene a Σ4P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}? (F14)
NO
QSAT1∈Σ1P⊆Σ4P\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_1 \in \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} \subseteq \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}
co-QSAT1∈Σ3P\mathrm{co\text{-}QSAT}_1 \in \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}? (SE23)
SÌ
co-QSAT1∈Π1P⊆Π2P⊆Σ3P\mathrm{co\text{-}QSAT}_1 \in \htmlData{term=Π1}{\Pi_1^{\mathrm{P}}} \subseteq \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}
Supponiamo Π2P⊂EXP\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} \subset \htmlData{term=EXP}{\mathrm{EXP}}. È vero che PRIMES non è EXP-hard? (F01)
SÌ
ipotesi irrilevante: PRIMES∈P⊊EXP\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}
TSP(D) è Π1P\htmlData{term=Π1}{\Pi_1^{\mathrm{P}}}-hard? (F14)
altro: solo se NP=coNP\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}} (PH=NP\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\mathrm{NP}})
TSP(D) NP-completo; se fosse coNP-hard coNP⊆NP\htmlData{term=coNP}{\mathrm{coNP}} \subseteq \htmlData{term=NP}{\mathrm{NP}}, cioè NP=coNP\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}}
È vero che QSAT3\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3 non è coNP-hard? (G16)
NO
QSAT3\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_3 è Σ3P\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}-completo e coNP=Π1P⊆Σ3P\htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=Π1}{\Pi_1^{\mathrm{P}}} \subseteq \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}
2-COL è PH-hard? (MA23)
altro: solo se PH=P\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=P}{\mathrm{P}}
2-COL∈P\htmlData{term=problem:COL2}{2\text{-}\mathrm{COL}} \in \htmlData{term=P}{\mathrm{P}}; PH-hard implicherebbe PH⊆P\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=P}{\mathrm{P}} (collasso al piano 0, P=NP\htmlData{term=P}{\mathrm{P}} = \htmlData{term=NP}{\mathrm{NP}}; a rigore anche =L= \htmlData{term=L}{\mathrm{L}})
QSAT2\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_2 è Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}-hard? (GE23)
SÌ
è Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}-completo
EXACT TSP è Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}-hard? (GE23)
altro: solo se DP=Σ2P\htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}
EXACT TSP è DP-completo e DP⊆Δ2P⊆Σ2P\htmlData{term=DP}{\mathrm{DP}} \subseteq \htmlData{term=Δ2}{\Delta_2^{\mathrm{P}}} \subseteq \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}; Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}-hard darebbe Σ2P⊆DP\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} \subseteq \htmlData{term=DP}{\mathrm{DP}}
Supponiamo PH=EXP\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}. MAX FLOW è PH-completo? (G16)
NO
MAX FLOW∈P\htmlData{term=problem:MAXFLOW}{\mathrm{MAX\ FLOW}} \in \htmlData{term=P}{\mathrm{P}}; PH-completo darebbe P=PH=EXP\htmlData{term=P}{\mathrm{P}} = \htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}, contro P⊊EXP\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}
Se PH=EXP\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}, PH collassa a un livello finito? (L18)
SÌ
PH⊆PSPACE⊆EXP=PH\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=PH}{\mathrm{PH}}, quindi PH=PSPACE\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}}; QSAT∈PH\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=PH}{\mathrm{PH}} sta in qualche ΣiP\Sigma_i^{\htmlData{term=P}{\mathrm{P}}}, quindi PH=ΣiP\htmlData{term=PH}{\mathrm{PH}} = \Sigma_i^{\htmlData{term=P}{\mathrm{P}}}
Supponiamo PH=EXP\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=EXP}{\mathrm{EXP}}. QSAT∈PH\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=PH}{\mathrm{PH}}? (SE23)
SÌ
QSAT∈PSPACE⊆EXP=PH\htmlData{term=problem:QSAT}{\mathrm{QSAT}} \in \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=EXP}{\mathrm{EXP}} = \htmlData{term=PH}{\mathrm{PH}}
Supponiamo Σ4P=Π4P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} = \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}. Σ4P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} non è strettamente contenuto in Π4P\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}? (F06)
SÌ
sono uguali, quindi nessun contenimento stretto
Supponiamo Π1P=Π4P\htmlData{term=Π1}{\Pi_1^{\mathrm{P}}} = \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}. NEXP⊆Π1P\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=Π1}{\Pi_1^{\mathrm{P}}}? (F07)
NO
l'ipotesi fa collassare PH=coNP=NP\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=coNP}{\mathrm{coNP}} = \htmlData{term=NP}{\mathrm{NP}}, quindi servirebbe NEXP⊆NP\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=NP}{\mathrm{NP}}, contro NP⊊NEXP\htmlData{term=NP}{\mathrm{NP}} \subsetneq \htmlData{term=NEXP}{\mathrm{NEXP}} (gerarchia nondeterministica). L'ipotesi non serve nemmeno: NP⊆NEXP⊆coNP\htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=coNP}{\mathrm{coNP}} darebbe comunque NP=coNP\htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=coNP}{\mathrm{coNP}} e di nuovo NEXP⊆NP\htmlData{term=NEXP}{\mathrm{NEXP}} \subseteq \htmlData{term=NP}{\mathrm{NP}}
Supponete che co-QSAT2\mathrm{co\text{-}QSAT}_2 non sia PH-hard. PSPACE=Π2P\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}? (F02)
NO
se PSPACE=Π2P\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} allora PH=Π2P\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} e il Π2P\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}}-completo co-QSAT2\mathrm{co\text{-}QSAT}_2 sarebbe PH-hard, contro l'ipotesi
Supponiamo Π2P=PH\htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} = \htmlData{term=PH}{\mathrm{PH}}. È vero che non esistono riduzioni da QSAT4\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_4 a co-QSAT4\mathrm{co\text{-}QSAT}_4? (F13)
NO
collasso al livello 2: Σ4P=Π4P\htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}} = \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}, quindi QSAT4∈Π4P\htmlData{term=problem:QSAT}{\mathrm{QSAT}}_4 \in \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}} si riduce al Π4P\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}-completo co-QSAT4\mathrm{co\text{-}QSAT}_4
Supponiamo VALIDITY riducibile a TSP(D). È vero che EXACT TSP non è Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}-completo? (F14)
NO
VALIDITY coNP-completo ≤TSP(D)∈NP⇒NP=coNP⇒PH=NP\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 DP=NP=Σ2P\htmlData{term=DP}{\mathrm{DP}} = \htmlData{term=NP}{\mathrm{NP}} = \htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}} e il DP-completo EXACT TSP è Σ2P\htmlData{term=Σ2}{\Sigma_2^{\mathrm{P}}}-completo
Assumiamo PH=NEXP\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NEXP}{\mathrm{NEXP}}. È vero che PRIMES non è NPSPACE-hard? (E26)
SÌ
PH⊆PSPACE⊆NEXP=PH\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}} \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}} = \htmlData{term=PH}{\mathrm{PH}}, quindi PSPACE=NEXP\htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=NEXP}{\mathrm{NEXP}}. PRIMES∈P\htmlData{term=problem:PRIMES}{\mathrm{PRIMES}} \in \htmlData{term=P}{\mathrm{P}}: se fosse NPSPACE-hard P=PSPACE=NEXP⊇EXP\htmlData{term=P}{\mathrm{P}} = \htmlData{term=PSPACE}{\mathrm{PSPACE}} = \htmlData{term=NEXP}{\mathrm{NEXP}} \supseteq \htmlData{term=EXP}{\mathrm{EXP}}, contro P⊊EXP\htmlData{term=P}{\mathrm{P}} \subsetneq \htmlData{term=EXP}{\mathrm{EXP}}
Supponiamo co-QSAT4∈Σ3P\mathrm{co\text{-}QSAT}_4 \in \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}}. Σ3P≠Σ4P\htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} \neq \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}? (FE23)
NO
Π4P⊆Σ3P\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}} \subseteq \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} ⇒\Rightarrow collasso al livello 3 ⇒Σ3P=Σ4P\Rightarrow \htmlData{term=Σ3}{\Sigma_3^{\mathrm{P}}} = \htmlData{term=Σ4}{\Sigma_4^{\mathrm{P}}}

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