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.

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:

Δ_{0}^{P} := Σ_{0}^{P} := Π_{0}^{P} := P,

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

Δ_{i + 1}^{P} := P^{Σ_{i}^{P}}

Σ_{i + 1}^{P} := {N P}^{Σ_{i}^{P}}

Π_{i + 1}^{P} := {c o N P}^{Σ_{i}^{P}}

dove $P^{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 $C$ ; le classi ${N P}^{C}$ e ${c o N P}^{C}$ sono definite in modo analogo. Ad esempio, abbiamo che $Σ_{1}^{P} = N P$ , $Π_{1}^{P} = c o N P$ , e $Δ_{2}^{P} = P^{N P}$ è la classe dei problemi risolvibili in tempo polinomiale da una macchina di Turing deterministica con un oracolo per qualche problema NP-completo.

Infine, la classe PH è definita come l'unione di tutti i livelli: $PH = ⋃_{k \geq 0} Σ_{k}^{p}$ .

Relazioni tra classi della gerarchia polinomiale

Dalle definizioni delle varie classi si ottengono le seguenti relazioni:

Σ_{i}^{P} \subseteq Δ_{i + 1}^{P} \subseteq Σ_{i + 1}^{P}

Π_{i}^{P} \subseteq Δ_{i + 1}^{P} \subseteq Π_{i + 1}^{P}

Σ_{i}^{P} = c o Π_{i}^{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 $k$ si avesse $Σ_{k}^{P} = Σ_{k + 1}^{P}$ o $Σ_{k}^{P} = Π_{k}^{P}$ , allora la gerarchia "collasserebbe" al livello $k$ , ovvero: per ogni $i > k$ , $Σ_{i}^{P} = Σ_{k}^{P}$ . In particolare, sono vere le seguenti implicazioni riguardanti problemi aperti:

$P = NP$ se e solo se $P = PH$ .
Se $NP = co-NP$ , allora $NP = PH$ .

Problemi completi

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

Chiaramente, rimuovendo il limite di $k$ (ovvero, ammettendo un qualunque numero e disposizione di quantificatori), il problema diventa PSPACE-completo.

Note

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

Bibliografia

(EN) S. Arora e B. Barak, Computational Complexity: 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

Portale Informatica

Portale Matematica

[1] Meyer-Stockmeyer, 1972

[Stockmeyer76-2] 1 2 Stockmeyer, 1976

[3] (EN) M. Schaefer e Christopher Umans, Completeness in the Polynomial-Time Hierarchy: A Compendium, 5 ottobre 2008.

[AroraBarak-4] 1 2 3 Arora-Barak, 2009

[5] (EN) Lane Hemaspaandra, 17.5 Complexity classes, in Kenneth H. Rosen (a cura di), Handbook of Discrete and Combinatorial Mathematics, Discrete Mathematics and Its Applications, 2nd, CRC Press, 2018, pp. 1308–1314, ISBN 9781351644051.