title: Tempo pseudopolinomiale
text: # 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.
  
  