Qual è la teoria della complessità computazionale?
La teoria della complessità computazionale è un'area della matematica e dell'informatica che si occupa delle risorse necessarie per risolvere i problemi su un sistema informatico. Sono disponibili diverse tecniche per determinare i requisiti di risorse di un problema. Alcuni problemi potrebbero non essere fattibili sui sistemi informatici esistenti a causa delle loro esigenze di risorse. I ricercatori classificano i problemi in base alla difficoltà e possono dividere i calcoli in problemi polinomiali (P) rispetto a polinomi non termministici (NP).
La risoluzione di un calcolo richiede risorse come tempo, spazio di archiviazione e hardware. Un sistema informatico potrebbe avere limitazioni che rendono un problema funzionalmente impossibile da risolvere perché non dispone delle risorse disponibili. Con il miglioramento della tecnologia informatica, un problema precedentemente irrisolvibile potrebbe diventare risolvibile con l'aiuto di nuove tecnologie e ricerche nel campo della teoria della complessità computazionale. La solvibilità di un problema non è necessariamente determinata dalla sua complessità ma dagli algoritmi utilizzati per risolverlo.
Nella teoria della complessità computazionale, un problema P può essere risolto in un tempo polinomiale con un algoritmo semplice. Potrebbe richiedere risorse sostanziali, ma è sia risolvibile che verificabile tramite computer. Tali problemi possono essere considerati risolvibili rapidamente fintanto che un computer ha le risorse disponibili per gestire i calcoli necessari.
I problemi NP sono più complessi. Non è possibile applicare un singolo algoritmo e potrebbe essere necessario utilizzare opzioni più avanzate, come le macchine di Turing parallele che possono esplorare diverse opzioni. Il problema potrebbe essere risolvibile in questo modo, ma richiederà sostanzialmente più risorse. Tali problemi potrebbero essere più facili per gli operatori umani che sono in grado di pensare logicamente avanzato, perché il punto di non ritorno è spesso quello della logica piuttosto che della semplice difficoltà di calcolo. Il problema del venditore ambulante, in cui l'obiettivo è quello di trovare il percorso più efficiente tra un certo numero di città lungo un percorso, è un classico esempio di problema NP nella teoria della complessità computazionale.
La classificazione dei problemi P rispetto a NP attraverso la teoria della complessità computazionale può essere un compito complesso e i problemi potrebbero spostarsi avanti e indietro attraverso la divisione. Una piccola serie di problemi computazionali non si adatta perfettamente a nessuna delle due categorie e talvolta viene classificata come nessuna delle due per riflettere ciò. Potrebbe eventualmente essere possibile sviluppare un algoritmo per risolvere un problema NP e, in alcuni casi, potrebbe applicarsi ad altri problemi che hanno una struttura simile. In altri, tuttavia, potrebbe essere specifico del problema. Il processo di esplorazione di tali programmi e lo sviluppo di approcci per risolverli è un'area importante della matematica e dell'informatica che contribuisce allo sviluppo di sistemi informatici avanzati e ad alta potenza.