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]

Note

1. ^ Meyer-Stockmeyer, 1972
2. Stockmeyer, 1976
3. ^ (EN) M. Schaefer e Christopher Umans, Completeness in the Polynomial-Time Hierarchy: A Compendium, 5 ottobre 2008.
4. Arora-Barak, 2009
5. ^ (EN) Lane Hemaspaandra, 17.5 Complexity classes, in Handbook of Discrete and Combinatorial Mathematics, 2nd, CRC Press, 2018, pp. 1308–1314, ISBN 9781351644051.

Bibliografia

• (EN) S. Arora e B. Barak, Complexity Theory: A Modern Approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4.
• (EN) A. R. Meyer e L. J. Stockmeyer, The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, 1972, pp. 125-129, DOI:10.1016/0304-3975(76)90061-X.
• (EN) L. J. Stockmeyer, The polynomial-time hierarchy, in Theoretical Computer Science, vol. 3, 1976, pp. 1-22, DOI:10.1016/0304-3975(76)90061-X.
• (EN) C. Papadimitriou, Chapter 17. Polynomial hierarchy, in Computational Complexity, Addison-Wesley, 1994, pp. 409-438, ISBN 978-0-521-42426-4.
• (EN) M. R. Garey e D. S. Johnson, Section 7.2: The Polynomial Hierarchy, in Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, pp. 161-167, ISBN 0-7167-1045-5.

Voci correlate

• P (complessità), NP (complessità), co-NP
• Teoria della complessità
• Teorema di Toda
• Formula booleana quantificata

  Portale Informatica

  Portale Matematica