Classe di complessità P

Nella classe di complessità P sono compresi i problemi polinomiali deterministici. Il problema può essere risolto dall'elaboratore (algoritmo) in tempi accettabili. L'algoritmo formula una soluzione e la verifica, restituendo un risultato in un tempo polinomiale rispetto al dato di input.

Esempio di problema di classe P. Si ipotizzi di voler calcolare l'insieme dei divisori interi di un numero n. Per individuare l'insieme dei divisori è sufficiente verificare ogni numero intero inferiore o uguale al numero n, effettuare la divisione e verificare se il resto è nullo oppure no. Quanto maggiore è il numero n tanto più lungo sarà il tempo di esecuzione dell'algoritmo che, in ogni caso, formulerà la risposta in un tempo polinomiale rispetto al dato di input.

La classe di complessità P è anche conosciuta come la classe dei "problemi facili" per sottolineare la differenza con l'altra classe di complessità NP ("problemi difficili") nell'analisi della complessità dei problemi.