La gerarchia polinomiale: tra problemi aperti e teoria dei giochi cooperativi

Da quando fu costruito il primo computer, l’uomo ha cominciato ad apprezzarne ed esplorarne le potenzialità. In questo contesto risultò naturale la nascita della disciplina della complessità computazionale, la quale si occupa di studiare quante risorse in termini di spazio e di tempo i vari problemi dell’informatica necessitino per la loro soluzione. Fu così che ebbero origine le prime classi di complessità che riunivano i problemi in base alla loro complessità (temporale e spaziale). La complessità strutturale nacque poi con l’obiettivo di analizzare le relazioni e i contenimenti tra le varie classi di complessità. In questo breve elaborato presenteremo una famiglia di classi di complessità temporale, la gerarchia polinomiale, vedremo alcune sue curiose ed interessanti proprietà ed esamineremo alcuni problemi nati dalla teoria dei giochi cooperativi e collocabili proprio in tale famiglia. Il primo capitolo sarà una rapida introduzione alla teoria della complessità computazionale, mentre nei successivi entreremo nel cuore dei vari argomenti: il secondo sarà incentrato appunto sulla gerarchia polinomiale (si faccia particolare attenzione alle sue caratteristiche peculiari, che la legano a doppio filo al famoso problema del millennio P vs NP); il terzo ed ultimo capitolo tratterà di teoria dei giochi cooperativi e in esso ci concentreremo sui concetti di Bargaining Set e di Kernel di un gioco a grafo e vedremo come la computazione di tali concetti di soluzione sia classificabile proprio nella gerarchia polinomiale.