La teoria della complessità è una branca della ricerca operativa che si occupa di quantificare la complessità di un algoritmo. La complessità di un algoritmo viene misurata in funzione del numero di passi necessari a risolvere un determinato problema da parte di un algoritmo. In genere la complessità di un algoritmo viene espressa in funzione della dimensione dei suoi dati di ingresso. Così si dirà che un algoritmo ha complessità O(n), cioè proporzionale ad n, se il tempo necessario per la sua esecuzione è proporzionale a n, dove n è il numero di dati del problema. Si è dimostrato che alcuni problemi sono intrinsecamente più complessi di altri, alcuni addirittura che richiedano un tempo di elaborazione infinito per la loro soluzione. Così sono state individuate due classi di problemi, quelli polinomiali, e quelli non polinomiali, cioè quelli che richiedono un tempo polinomiale per essere risolti e quelli che invece richiedono un tempo esponenziale. Un problema tutt’ora aperto è dimostrare se esista un modo per concepire un algoritmo che sia in grado di risolvere in un tempo polinomiale un problema di complessità esponenziale. Cioè, è possibile che i problemi siano tutti facili da risolvere o esistono problemi più difficili che con l’attuale matematica non riusciremo mai a risolvere in un tempo polinomiale ?
Tratto dal libro ‘La programmazione’ – guida per non addetti.