Gerarchia polinomiale

La gerarchia polinomiale è, nella teoria della complessità computazionale, una gerarchia di classi di complessità che estende e generalizza le classi P, NP e co-NP, definita mediante l'alternanza di quantificatori o tramite macchine di Turing con oracoli. Venne formalizzata negli anni 1970.^[1][2]

Ogni classe nella gerarchia è contenuta in PSPACE. L'unione delle classi facenti parte della gerarchia, che a sua volta forma una classe di complessità, è indicato con PH (dall'inglese polynomial hierarchy). È tuttora ignoto se PH sia una gerarchia propria (cioè se tutte le inclusioni siano strette) o se collassi a qualche livello finito.

Definizione

Le classi della gerarchia sono definite in modo ricorsivo. Prima di tutto, definiamo:

${\displaystyle \Delta _{0}^{\mathrm {P} }:=\Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P} ,}$

dove P è la classe di problemi decisionali risolvibili in tempo polinomiale da una macchina di Turing deterministica. Poi, per qualunque intero ${\displaystyle i\geq 0}$, definiamo:

${\displaystyle \Delta _{i+1}^{\mathrm {P} }:=\mathrm {P} ^{\Sigma _{i}^{\mathrm {P} }}}$

${\displaystyle \Sigma _{i+1}^{\mathrm {P} }:=\mathrm {NP} ^{\Sigma _{i}^{\mathrm {P} }}}$

${\displaystyle \Pi _{i+1}^{\mathrm {P} }:=\mathrm {coNP} ^{\Sigma _{i}^{\mathrm {P} }}}$

dove ${\displaystyle \mathrm {P} ^{\rm {C}}}$ è l'insieme di problemi decisionali risolvibili in tempo polinomiale da una macchina di Turing deterministica con un oracolo per qualche problema completo per la classe ${\displaystyle C}$; le classi ${\displaystyle \mathrm {NP} ^{\rm {C}}}$ e ${\displaystyle \mathrm {coNP} ^{\rm {C}}}$ sono definite in modo analogo. Ad esempio, abbiamo che ${\displaystyle \Sigma _{1}^{\mathrm {P} }=\mathrm {NP} }$, ${\displaystyle \Pi _{1}^{\mathrm {P} }=\mathrm {coNP} }$, e ${\displaystyle \Delta _{2}^{\mathrm {P} }=\mathrm {P^{NP}} }$ è la classe dei problemi risolvibili in tempo polinomiale da una macchina di Turing deterministica con un oracolo per qualche problema NP-completo.^[3]

Infine, la classe PH è definita come l'unione di tutti i livelli: ${\displaystyle {\textrm {PH}}=\bigcup _{k\geq 0}\Sigma _{k}^{p}}$.^[4]

Relazioni tra classi della gerarchia polinomiale

Diagramma che mostra le relazioni di inclusione tra le varie classi della gerarchia polinomiale

Dalle definizioni delle varie classi si ottengono le seguenti relazioni:

${\displaystyle \Sigma _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Sigma _{i+1}^{\mathrm {P} }}$

${\displaystyle \Pi _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Pi _{i+1}^{\mathrm {P} }}$

${\displaystyle \Sigma _{i}^{\mathrm {P} }=\mathrm {co} \Pi _{i}^{\mathrm {P} }}$

A differenza della gerarchia aritmetica e analitica, le cui inclusioni sono note essere proprie, rimane una domanda aperta se anche quelle della gerarchia polinomiale lo sono, sebbene tale congettura sia generalmente ritenuta vera. Se per qualunque ${\displaystyle k}$ si avesse ${\displaystyle \Sigma _{k}^{\mathrm {P} }=\Sigma _{k+1}^{\mathrm {P} }}$ o ${\displaystyle \Sigma _{k}^{\mathrm {P} }=\Pi _{k}^{\mathrm {P} }}$, allora la gerarchia "collasserebbe" al livello ${\displaystyle k}$, ovvero: per ogni ${\displaystyle i>k}$, ${\displaystyle \Sigma _{i}^{\mathrm {P} }=\Sigma _{k}^{\mathrm {P} }}$.^[4] In particolare, sono vere le seguenti implicazioni riguardanti problemi aperti:

• ${\displaystyle {\textrm {P}}={\textrm {NP}}}$ se e solo se ${\displaystyle {\textrm {P}}={\textrm {PH}}}$.^[5]
• Se ${\displaystyle {\textrm {NP}}={\textrm {co-NP}}}$, allora ${\displaystyle {\textrm {NP}}={\textrm {PH}}}$.

Problemi completi

Un esempio canonico: il problema di soddisfacibilità per formule booleane con ${\displaystyle k}$ alternanze di quantificatori (una forma limitata di QBF) è completo per ${\displaystyle \Sigma _{k}^{p}}$ o ${\displaystyle \Pi _{k}^{p}}$, a seconda che la formula inizi con ${\displaystyle \exists }$ o ${\displaystyle \forall }$, rispettivamente.^[2]