Complessità computazionale

[Il presente è liberamente tratto da qui]

I teorici della computazione studiano quanto tempo e memoria siano necessari per far girare algoritmi che trovino o controllino la validità di una soluzione ad un dato problema. Tante sono le categorie di problemi; i teorici della computazione cercano di catalogarli a seconda che richiedano risorse ragionevoli (di tempo e memoria) o nel caso in cui non siano efficienti. A seconda di precise distinzioni matematiche i problemi matematici si dividono in varie classi di complessità. Ad esempio con "P" si intende l’insieme dei problemi per la risoluzione dei quali è noto un algoritmo che, dato un qualsiasi input iniziale espresso in n bits, trova una soluzione in tempo polinomiale, ossia in un tempo non più lungo di n^k per qualche k intero. In quanto segue sostituirò la parola "polinomiale" con la parola "ragionevole", come contrapposte a "esponenziale" o "esagerato", e fregatevene dell’esempio.

Esempio. Per fare un prodotto "in colonna" tra due numeri di massimo n/2 cifre dovete moltiplicare ogni cifra del secondo per ogni cifra del primo, un compito che richiede un numero di passaggi proporzionale ad n^2, dovete sommare i risultati e i riporti opportunamente incolonnati, un compito che richiede un numero proporzionale ad n passaggi. La moltiplicazione di due numeri qualsiasi è un problema di classe P.

Non-riutilizzabilità del tempo

I teorici della computazione congetturano che PSPACE sia sostanzialmente più grande di P, ed il motivo dovrebbe risiedere nel fatto che la memoria può essere cancellata e riscritta, mentre il tempo va avanti inesorabile. Il tempo non è riutilizzabile, la memoria si, sempre che contenga informazioni non più necessarie per proseguire; quindi posso ottimizzarne l’utilizzo. Ora da un punto di vista fisico la memoria sarà supportata da un hardware esteso nello spazio: è così che arriviamo a concepire la differenza tra tempo e spazio di cui abbiamo parlato nella precedente puntata: io posso tornare in istanti diversi nello stesso posto, non posso essere nello stesso istante in diversi posti.

E se invece il tempo fosse riutilizzabile? Scott Aaronson e John Watrous hanno mostrato recentemente che se facciamo in modo che il tempo sia riutilizzabile le due classi diventano banalmente equivalenti. E’ questo che loro prendono come indizio per sostenere che tempo e spazio devono essere sostanzialmente diversi, se crediamo che la teoria della computazione non sia solo un’enorme banalità. Come si può tornare indietro nel tempo (ovviamente da un punto di vista puramente matematico-speculativo)? Beh un modo è di pensare che si possa semplicemente invertire il fluire del tempo quando si preferisce, così come è possibile invertire la propria direzione di marcia. In questo caso abbiamo risolto il problema della non-riutilizzabilità del tempo, che diventa nient’altro che un’altra identica dimensione spaziale, e quindi risulta ovvio che le due classi siano equivalenti. In maniera meno ovvia, si può ipotizzare di poter tornare indietro nel tempo come con una macchina del tempo, compiendo cicli, sfruttando "curve temporali chiuse" che tornano su se stesse e permettano di "rivivere" un precedente istante e di utilizzarlo in altra maniera. Per essere rigorosi bisogna che questo viaggio indietro nel tempo sia consistente, cioè che non si creino paradossi del tipo "uccido mio nonno" o cose del genere.

Aaronson e Watrous hanno mostrato che se esistono queste curve temporali chiuse contenenti quantità ragionevoli di tempo, allora il tempo diventa una risorsa esattamente equivalente allo spazio come riserva di memoria e PSPACE = P. In questo caso, inoltre, la computazione classica e quella quantistica risultano equivalenti.