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 ${\displaystyle W}$ in una base ${\displaystyle b\geq 2}$ sono necessari almeno ${\displaystyle \lceil \log _{b}{W}\rceil }$ bits. Perciò in genere il valore ${\displaystyle 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.

Consideriamo il problema del verificare se un numero ${\displaystyle n}$ è primo. Un approccio banale è quello di verificare se i numeri nell'insieme ${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$ dividono ${\displaystyle n}$ (con resto 0). Questo approccio richiede ${\displaystyle {\sqrt {n}}-1}$ operazioni di divisione, ovvero un numero sublineare nel valore di ${\displaystyle n}$ ma non nella sua dimensione. Infatti, rappresentando ${\displaystyle n}$ con ${\displaystyle \log {n}}$ bits avremo che il tempo di esecuzione dell'algoritmo (in funzione della grandezza dell'istanza in input) sarà ${\displaystyle O(2^{\sqrt {n}})}$.

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

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

Più formalmente, i vincoli del problema sono:

• maximize ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$
• subject to ${\displaystyle \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 ${\displaystyle O(nW)}$. Dato che ${\displaystyle W}$ è un valore dato come parametro in input, esso verrà rappresentato con non meno di ${\displaystyle \log {W}}$ bits. Perciò tale algoritmo computa effettivamente in tempo esponenziale rispetto alla dimensione dell'input.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica