La teoria della complessità computazionale
La teoria della complessità computazionale è la disciplina dell'informatica teorica che si occupa di studiare e classificare la difficoltà a risolvere dei problemi.
In generale, alcuni problemi sono abbastanza semplici da risolvere.
Altri problemi, invece, richiedono molte risorse e tempo per giungere a una soluzione, con diversi livelli crescenti di difficoltà fino a diventare impossibili da risolvere.
Ad esempio, l'ordinamento crescente dei numeri è un problema molto semplice. In una frazione di secondo un PC può ordinare una lista composta da milioni di numeri. Viceversa, il problema dello zaino e la fattorizzazione dei numeri molto grandi sono problemi molto più difficili e complessi da risolvere. Alcuni problemi richiederebbero secoli o millenni di elaborazione e una memoria più grande dell'intero universo. Giusto per rendere l'idea...
Cosa rende un problema facile e un altro difficile?
La domanda è semplice... ma la risposta è complicata. E forse non c'è nemmeno una risposta.
Per questa ragione la teoria della complessità è ancora un campo di studio aperto, dove sono impegnati migliaia di ricercatori in tutto il mondo.
Quello che sappiamo è che esistono diverse "classi di difficoltà computazionale" a cui appartengono i problemi.
- P: E' la classe dei problemi risolvibili da un algoritmo entro un tempo polinomiale. Sono i problemi considerati "facilmente" risolvibili.
- NP: Sono problemi nei quali possiamo "verificare" in tempo polinomiale se una soluzione è giusta ma non è detto che esista un algoritmo in grado di "trovare" la soluzione in tempo polinomiale. Questa classe comprende anche i problemi P.
- NP-Completo: E' una sottoclasse dei problemi NP che include i problemi più difficili. Se trovassimo la soluzione a questi problemi... avremmo risolto anche tutti gli altri.
Oltre a queste classi ce ne sono molte altre. Le classi P, NP, e NP-completo sono soltanto quelle principali.
Gli approcci ai problemi computazionalmente difficili
Quando un problema è computazionalmente difficile si possono seguire diverse strade.
La prima strada è quella della teoria computazionale. Si ricerca la causa che rende "difficile" il problema e si modifica il problema rendendolo più facilmente risolvibile.
La seconda strada consiste nella ricerca delle soluzioni sub-ottimali.
Ci si accontenta di una soluzione "accettabile" (sub-ottimale) perché quella "ottimale" richiederebbe troppe risorse in termini di memoria e tempo di elaborazione.
Inoltre, alcuni problemi sono difficili solo nel caso peggiore, mentre sono risolvibili facilmente nella maggior parte dei casi. In questo caso potremmo accettare il rischio di affrontare un calcolo più lento di tanto in tanto.
Ad esempio, se devo analizzare un file composto da miliardi di dati, potrei accedere ai dati in modo random (casuale) e considerare valido il primo dato che soddisfa delle condizioni accettabili oppure interrompere la ricerca dopo n tentativi e accontentarmi del migliore risultato trovato.
Va detto che la prima strada, quella della ricerca della radice del problema, è sicuramente quella più difficile da percorrere ma anche quella che un giorno potrebbe forse risolvere tutti i problemi computazionali.
