Problemi P

I problemi P sono quei problemi computazionali per i quali esiste un algoritmo che può trovare una soluzione in tempo polinomiale rispetto alla dimensione dell'input.

In altre parole, per questi problemi, il tempo necessario per arrivare alla soluzione cresce in modo polinomiale (non esponenzialmente) all'aumentare delle dimensioni dell'input.

In un problema appartenente alla classe P, la complessità temporale per risolverlo può al massimo crescere come $ O(n^k) $, dove n è la dimensione dell'input e k è una costante positiva. 

Questo significa che il tempo necessario per risolvere il problema cresce al massimo come una potenza polinomiale della dimensione dell'input, rendendo tali problemi gestibili e risolvibili in tempi ragionevoli per valori di n praticamente rilevanti.

Nella teoria computazionale sono considerati problemi relativamente "facili" da risolvere con computer moderni, specialmente quando confrontati con problemi di classi più complesse come NP-completi o NP-difficili.

Esempio

Un esempio classico di problema nella classe P è l'ordinamento di un elenco.

Consideriamo il caso specifico dell'ordinamento tramite l'algoritmo Merge Sort.

Merge Sort è un algoritmo di ordinamento che adotta l'approccio divide et impera: divide l'elenco in metà, ordina ciascuna metà separatamente e poi fonde le due metà ordinate per ottenere l'elenco completo ordinato.

La complessità temporale di Merge Sort è $ O(n \log n) $, dove n è il numero di elementi nell'elenco.

Questo significa che il tempo necessario per ordinare l'elenco cresce logaritmicamente con la dimensione dell'elenco, una crescita molto contenuta e gestibile anche per grandi valori di n.

Essendo O(n log n) una forma polinomiale, l'ordinamento di un elenco con Merge Sort rientra nella definizione di problemi risolvibili in tempo polinomiale, e quindi appartiene alla classe P.