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 numerose tecniche per determinare i requisiti di risorse di un problema. Alcuni problemi potrebbero non essere fattibili sui sistemi informatici esistenti a causa della loro richiesta di risorse. I ricercatori classificano i problemi in base alla difficoltà e possono dividere i calcoli in problemi polinomiali (P) e non polinomiali (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 risolvibilità di un problema non è necessariamente determinata dalla sua complessità ma dagli algoritmi utilizzati per risolverlo.
Nella teoria della complessità computazionale, un problema P è un problema che può essere risolto in tempo polinomiale con un algoritmo semplice. Potrebbe ancora richiedere risorse sostanziali, ma è sia risolvibile che controllabile dal computer. Tali problemi potrebbero essere ritenuti risolvibili rapidamente purché un computer abbia 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 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 capaci di pensiero logico avanzato, perché il punto di svolta è spesso uno di logica piuttosto che una pura difficoltà di calcolo. Il problema del commesso viaggiatore, in cui l’obiettivo è trovare il percorso più efficiente tra un numero di città lungo un percorso, è un classico esempio di problema NP nella teoria della complessità computazionale.
La classificazione dei problemi P rispetto a quelli NP attraverso la teoria della complessità computazionale può essere un compito complesso e i problemi potrebbero spostarsi avanti e indietro attraverso il divario. Un piccolo insieme di problemi computazionali non si adatta perfettamente a nessuna delle due categorie e talvolta è classificato come nessuno dei due per riflettere questo. Potrebbe eventualmente essere possibile sviluppare un algoritmo per risolvere un problema di 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.