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 $W$ in una base $b\ge 2$ sono necessari almeno $\lceil {\log }_{b}W\rceil$ bits. Perciò in genere il valore $W$ è 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 $n$ è primo. Un approccio banale è quello di verificare se i numeri nell'insieme Template:Nowrap dividono $n$ (con resto 0). Questo approccio richiede Template:Nowrap operazioni di divisione, ovvero un numero sublineare nel valore di $n$ ma non nella sua dimensione. Infatti, rappresentando $n$ con $\log n$ bits avremo che il tempo di esecuzione dell'algoritmo (in funzione della grandezza dell'istanza in input) sarà $O(2^{\sqrt{n}})$.

Per esempio, se si volesse verificare con questo approccio la primalità di un numero $n$ leggermente più piccolo di $10^{10}$ servirebbero fino a $10^5$ operazioni (nel caso peggiore), nonostante per rappresentare $n$ servano solamente $32$ 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 $O({\log }^{6}n)$.

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 $W$. Abbiamo a disposizione $n$ items, ognuno dei quali avente un peso $w_i$ e un valore $v_i$. 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 $n$-dimensionale $\underset{\_}{x}=(x_1,...,x_n)$ composto dai soli valori 0 e 1, tale che $x_i=1$ se l'oggetto $i$-esimo verrà portato nello zaino, $0$ altrimenti.

Più formalmente, i vincoli del problema sono:

• maximize $\sum _{i=1}^n{v}_i{x}_i$
• subject to $\sum _{i=1}^n{w}_i{x}_i\le W$

È 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 $O(nW)$. Dato che $W$ è un valore dato come parametro in input, esso verrà rappresentato con non meno di $\log W$ bits. Perciò tale algoritmo computa effettivamente in tempo esponenziale rispetto alla dimensione dell'input.