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:

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

dove è 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 ; le classi e sono definite in modo analogo. Ad esempio, abbiamo che , , e è 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: .

Relazioni tra classi della gerarchia polinomiale

Dalle definizioni delle varie classi si ottengono le seguenti relazioni:

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 si avesse o , allora la gerarchia "collasserebbe" al livello , ovvero: per ogni , . In particolare, sono vere le seguenti implicazioni riguardanti problemi aperti: se e solo se . Se , allora .

Problemi completi Un esempio canonico: il problema di soddisfacibilità per formule booleane con alternanze di quantificatori (una forma limitata di QBF) è completo per o , a seconda che la formula inizi con o , rispettivamente.

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

Note

Bibliografia

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

Categoria:Teoria della complessità computazionale