La teoria della complessit\u00e0 \u00e8 una branca della ricerca operativa che si occupa di quantificare la complessit\u00e0 di un algoritmo. La complessit\u00e0 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\u00e0 di un algoritmo viene espressa in funzione della dimensione dei suoi dati di ingresso. Cos\u00ec si dir\u00e0 che un algoritmo ha complessit\u00e0 O(n), cio\u00e8 proporzionale ad n, se il tempo necessario per la sua esecuzione \u00e8 proporzionale a n, dove n \u00e8 il numero di dati del problema. Si \u00e8 dimostrato che alcuni problemi sono intrinsecamente pi\u00f9 complessi di altri, alcuni addirittura che richiedano un tempo di elaborazione infinito per la loro soluzione. Cos\u00ec sono state individuate due classi di problemi, quelli polinomiali, e quelli non polinomiali, cio\u00e8 quelli che richiedono un tempo polinomiale per essere risolti e quelli che invece richiedono un tempo esponenziale. Un problema tutt\u2019ora aperto \u00e8 dimostrare se esista un modo per concepire un algoritmo che sia in grado di risolvere in un tempo polinomiale un problema di complessit\u00e0 esponenziale. Cio\u00e8, \u00e8 possibile che i problemi siano tutti facili da risolvere o esistono problemi pi\u00f9 difficili che con l\u2019attuale matematica non riusciremo mai a risolvere in un tempo polinomiale ?<\/p>\n\n\n\n
Tratto dal libro ‘La programmazione’ – guida per non addetti.<\/p>\n\n\n\n