La teoria della calcolabilità divide i problemi in risolvibili e irrisolvibili. Ma un problema risolvibile in linea di principio può richiedere un tempo così lungo da essere inutile in pratica. La teoria della complessità introduce allora una seconda distinzione, fra problemi trattabili e intrattabili. La classe più importante dalla parte trattabile è P: l'insieme dei problemi decidibili in tempo polinomiale da una macchina deterministica.
La definizione
Per una macchina di Turing deterministica M che si ferma su ogni input, il tempo di esecuzione è la funzione t(n) che dà il numero massimo di passi compiuti da M su un input di lunghezza n. Si guarda il caso peggiore, non quello medio.
TIME(t(n)) è la classe dei linguaggi decisi da qualche macchina deterministica in tempo O(t(n)).
P = TIME(n) ∪ TIME(n²) ∪ TIME(n³) ∪ …
cioè l'unione di TIME(nᵏ) per ogni k. Un problema sta in P se esiste un algoritmo che lo risolve con un numero di passi limitato da un polinomio nella lunghezza dell'input.
Perché proprio il polinomio
La scelta del polinomio come confine può sembrare arbitraria: un algoritmo in n¹⁰⁰ non è certo pratico. Le ragioni sono più solide di quanto sembri.
- Robustezza rispetto al modello: una macchina multinastro si simula con una a un nastro con rallentamento quadratico; un modello a registri o un linguaggio di programmazione reale si simulano con rallentamento polinomiale. La classe P resta la stessa, qualunque modello ragionevole si usi.
- Chiusura per composizione: se un algoritmo polinomiale chiama un numero polinomiale di volte una subroutine polinomiale, il risultato è ancora polinomiale. Questo permette di costruire algoritmi complessi combinando pezzi semplici.
- Distacco dall'esponenziale: la differenza fra n³ e 2ⁿ è abissale. Raddoppiare la velocità di una macchina permette, con un algoritmo in n³, di risolvere istanze più grandi di circa il 26%; con un algoritmo in 2ⁿ, istanze più grandi di un solo elemento.
- Esperienza: quando per un problema naturale si trova un algoritmo polinomiale, spesso l'esponente viene poi ridotto a valori piccoli.
La codifica dell'input conta
«Lunghezza dell'input» significa numero di simboli usati per scriverlo, ed è qui che si nascondono molte trappole.
Un numero N scritto in binario occupa circa log₂ N bit. Un algoritmo che compie N passi è quindi esponenziale nella lunghezza dell'input, non lineare. Per esempio, verificare se N è primo provando tutti i divisori fino a √N richiede circa √N = 2^(log₂N / 2) passi: esponenziale nel numero di cifre.
Si richiede sempre una codifica ragionevole: binaria o decimale per i numeri, liste di nodi e archi o matrici di adiacenza per i grafi. La codifica unaria, in cui il numero 5 si scrive 11111, è considerata irragionevole perché gonfia artificialmente la lunghezza dell'input e rende polinomiali algoritmi che non lo sono.
Algoritmi pseudo-polinomiali
Il problema dello zaino (knapsack) con capacità W e n oggetti si risolve con la programmazione dinamica in tempo O(nW). Sembra polinomiale, ma W è un numero, e la sua scrittura binaria è lunga log W. Il tempo è quindi esponenziale nella lunghezza dell'input. Algoritmi di questo tipo si chiamano pseudo-polinomiali: sono veloci quando i numeri in gioco sono piccoli, ma non dimostrano che il problema stia in P.
Esempi di problemi in P
- Raggiungibilità in un grafo: dato un grafo orientato con due nodi s e t, esiste un cammino da s a t? Una visita in ampiezza esamina ogni nodo e ogni arco al più una volta.
- Numeri coprimi: dati x e y, il loro massimo comun divisore è 1? L'algoritmo di Euclide dimezza almeno uno dei numeri ogni due passi, quindi il numero di iterazioni è proporzionale al numero di cifre.
- Appartenenza a un linguaggio libero dal contesto: data una grammatica in forma normale di Chomsky e una stringa di lunghezza n, l'algoritmo CYK decide in tempo O(n³).
- Primalità: decidere se un numero scritto in binario è primo è in P. Lo ha dimostrato l'algoritmo AKS; è un caso in cui l'appartenenza a P non era affatto evidente.
- Programmazione lineare: ottimizzare una funzione lineare con vincoli lineari è in P, grazie al metodo dell'ellissoide e ai metodi a punto interno, anche se il metodo del simplesso, molto usato in pratica, ha casi peggiori esponenziali.
Che cosa P non garantisce
Appartenere a P è una garanzia teorica, non pratica. Un algoritmo in O(n⁸) con costanti grandi può essere inutilizzabile, mentre un algoritmo esponenziale ben ottimizzato può risolvere senza problemi tutte le istanze che interessano davvero. P misura come cresce il costo nel caso peggiore quando l'input cresce, e questo è un indicatore prezioso, ma non sostituisce le misure sul campo.
Nel mio lavoro la domanda «è in P?» serve soprattutto a scegliere la strategia: se un problema è in P cerco l'algoritmo giusto; se sembra non esserlo, cambio subito approccio e penso a vincoli, approssimazioni o limiti alle dimensioni.
In sintesi
- P è la classe dei problemi decidibili da una macchina deterministica in tempo polinomiale nel caso peggiore.
- Il polinomio come confine è robusto rispetto ai modelli di calcolo e chiuso per composizione.
- La lunghezza dell'input si misura con codifiche ragionevoli: un numero N occupa circa log N bit.
- Gli algoritmi pseudo-polinomiali, come quello per lo zaino, non dimostrano l'appartenenza a P.
- Raggiungibilità, coprimalità, CYK, primalità e programmazione lineare sono in P.
