Tempo pseudopolinomiale
In teoria della complessità computazionale, un algoritmo è detto pseudopolinomiale se la sua complessità temporale è polinomiale nel valore numerico del suo input e non necessariamente nella sua dimensione (ovvero il numero di bits necessari per la sua codifica).
Se si vuole rappresentare un intero in una base sono necessari almeno bits. Perciò in genere il valore è esponenziale nella sua grandezza.
Un problema NP-completo per il quale si conosce un algoritmo pseudopolinomiale che lo risolve è anche detto weakly NP-completo. È invece detto strongly NP-completo un problema NP-completo per il quale è dimostrato la non esistenza di un algoritmo pseudopolinomiale che lo risolve, a meno che P=NP.
Esempi
Test di primalità
Consideriamo il problema del verificare se un numero è primo. Un approccio banale è quello di verificare se i numeri nell'insieme dividono (con resto 0). Questo approccio richiede operazioni di divisione, ovvero un numero sublineare nel valore di ma non nella sua dimensione. Infatti, rappresentando con bits avremo che il tempo di esecuzione dell'algoritmo (in funzione della grandezza dell'istanza in input) sarà .
Per esempio, se si volesse verificare con questo approccio la primalità di un numero leggermente più piccolo di servirebbero fino a operazioni (nel caso peggiore), nonostante per rappresentare servano solamente bits (all'incirca).
Inoltre è facile creare un'istanza per la quale questo approccio non è affatto ragionevole: per esempio fissando un numero a 1024-bit.
Per fortuna, nel 2002 è stato scoperto un algoritmo che verifica la primalità di un numero in tempo [1].
Knapsack problem
Il Knapsack problem (noto in italiano come problema dello zaino o problema della bisaccia) è un problema di ottimizzazione combinatoria definito come segue:
- è dato uno zaino che può sopportare un peso massimo pari a una valore numerico . Abbiamo a disposizione items, ognuno dei quali avente un peso e un valore . L'obiettivo è quello di scegliere un sottoinsieme di oggetti da portare nello zaino in modo che il loro peso sia sostenibile, e tale che massimizzi il valore trasportato.
Una soluzione ammissibile può essere rappresentata da un vettore -dimensionale composto dai soli valori 0 e 1, tale che se l'oggetto -esimo verrà portato nello zaino, altrimenti.
Più formalmente, i vincoli del problema sono:
- maximize
- subject to
È noto che risolvere questo problema è NP-hard, perciò è impossibile trovare un algoritmo polinomiale a meno che P=NP. Esiste però un algoritmo di programmazione dinamica che risolve il problema in tempo . Dato che è un valore dato come parametro in input, esso verrà rappresentato con non meno di bits. Perciò tale algoritmo computa effettivamente in tempo esponenziale rispetto alla dimensione dell'input.
Note
- ^ (EN) L'articolo originale (PDF), su cse.iitk.ac.in.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)