Classi di complessità

Le classi di complessità sono problemi di difficile soluzione analizzati nell'analisi della complessità e studiati nella teoria delle complessità computazionale. Le principali classi di complessità dei problemi sono le seguenti:

• Classe di complessità P. Sono problemi polinomiali deterministici. Questi problemi sono risolvibili da una macchina deterministica in un tempo polinomiale rispetto alla dimensione dei dati di input. L'algoritmo riesce ad individuare una soluzione ed a verificarla in un tempo polinomiale.
• Classe di complessità NP. Sono problemi polinomiali non deterministici. Questi problemi sono risolvibili da una macchina non deterministica in un tempo polinomiale avendo le giuste informazioni. Nell'insieme dei problemi NP è compreso l'insieme dei problemi P e un insieme di problemi NP-completi.

Le due classi di complessità possono essere rappresentate graficamente utilizzando gli strumenti messi a disposizione dalla teoria degli insiemi.

La classe di complessità P è un sottoinsieme della classe di complessità NP. Questa caratteristica ha spinto alcuni autori ad ipotizzare l'uguaglianza dei problemi di classe P e NP nel caso di infinita capacità computazionale degli elaboratori. Tuttavia, tale ipotesi è fortemente criticata a causa della presenza dei problemi NP Completi. Questi ultimi sono una sottoclasse di problemi NP particolarmente estremi ("difficili") che non consentono d'essere trattati come problemi di tipo P.