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\geq 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 $\{2,3,\dots ,{\sqrt {n}}\}$ dividono $n$ (con resto 0). Questo approccio richiede ${\sqrt {n}}-1$ 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 2022 è 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 ${\underline {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}\leq 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.