Algoritmo polinomiale
Un algoritmo polinomiale è un algoritmo in grado di completare l'elaborazione di una dimensione n di dati in ingresso in un tempo di esecuzione pari a O ( nk ) dove k è un numero intero positivo. In tali casi si dice che l'algoritmo completa l'esecuzione in un tempo polinomiale ed è calcolabile in tempo polinomiale. Gli algoritmi calcolabili in tempo polinomiale ( algoritmo tempo-polinomiale ) sono considerati algoritmi efficienti poiché, rispetto ai meno efficienti algoritmi tempo-esponenziali, consentono un significativo aumento del tempo di esecuzione dell'algoritmo quando aumenta la velocità di calcolo dell'elaboratore. Ad esempio, la funzione di complessità di un algoritmo polinomiale può essere la seguente: O ( n2 ). In tale caso, ipotizzando che ogni istruzione sia elaborata in un'unità di tempo ( es. nanosecondo ), l'algoritmo impiega n2 unità di tempo per elaborare n dati. Gli algoritmi polinomiali sono classificati in:
- Algoritmo polinomiale forte. L'algoritmo si dice polinomiale forte se esiste un numero intero k tale che l'algoritmo impiega un tempo O ( nk ) per elaborare qualsiasi dato in input che consista in n numeri.
- Algoritmo polinomiale debole. L'algoritmo polinomiale debole è un algoritmo polinomiale che non rispetta le condizioni per essere un algoritmo polinomiale forte.
Quando un problema può essere risolto in un tempo polinomiale è detto problema P o problema di tipo P, dove la lettera P indica per l'appunto "polinomiale". Un esempio di problema P è l'ordinamento ( sort ) di n valori. Quando un problema può essere risolto in un tempo polinomiale soltanto nella ipotesi migliore ( algoritmo di Gastone ) è invece detto problema NP o problema non deterministico di tipo P. Ad esempio, un problema NP termina la sua esecuzione in tempo-polinomiale ( es. pochi minuti ) se la soluzione si trovasse tra le prime combinazioni di dati ad essere analizzate. Viceversa, se la soluzione si trovasse tra le ultime combinazioni di dati da analizzare e l'insieme delle combinazioni fosse infinitamente grande, allora lo stesso algoritmo polinomiale richiederebbe un tempo di esecuzione non polinomiale e infinitamente grande ( es. secoli o millenni ).
Problema NP. È errato definire il problema di tipo NP come problema non polinomiale. Il problema NP è anch'esso un problema polinomiale. Il problema NP si distingue dal problema P per la sua natura non deterministica e per il tempo di esecuzione non polinomiale.
