Analisi della complessità

L'analisi della complessità studia la complessità dei problemi. Si distingue da quella degli algoritmi in quanto non analizza la procedura utilizzata per la risoluzione di un problema (algoritmo) bensì la complessità stessa del problema. I problemi sono classificati in classi di complessità P e NP indipendentemente dall'algoritmo utilizzato. L'analisi della complessità ha lo scopo di stabilire se un problema può essere affrontato da un algoritmo, ossia se l'algoritmo può formulare una soluzione al problema e verificare l'ipotesi in un tempo polinomiale accettabile.