Complessità del calcolo

Note

La complessità del calcolo ci permette di razionalizzare i concetti di costo di una computazione (tempo e memoria), e misura e confronto del costo di soluzioni ad un problema.

Per la tesi di Church-Turing, un problema è calcolabile o meno indipendentemente dallo strumento usato. Non si ha una “tesi di Church-Turing” della complessità. Ci serve uno strumento per valutare la complessità temporale e spaziale che tralasci “considerazioni superflue” e utilizzabile per la maggioranza dei modelli di calcolo.

Complessità temporale e spaziale

Note

Data la computazione $c_0\stackrel{\ast }{⊢}{c}_r$ di $\mathcal{M}$, la complessità temporale di è $T_{\mathcal{M}}(x)=r$ se $\mathcal{M}$ si ferma in un dato $c_r$, $\infty$ altrimenti. La complessità spaziale è definita come $S_{\mathcal{M}}(x)=\sum _{j=1}^k{\max }_{i\in \{0,\cdots ,r\}}(|a_{ij}|)$ con $|a_{ij}|$ lunghezza del contenuto del $j$-esimo nastro alla mossa $i$-esima, cioè la somma delle quantità di nastro occupate, per ogni nastro.

Sotto opportune ipotesi, è possibile semplificare da $T_{\mathcal{M}}(x)$ e $S_{\mathcal{M}}(x)$ a $T_{\mathcal{M}}(n)$ e $S_{\mathcal{M}}(n)$, dove $n$ è la lunghezza dell’input. Generalmente scegliamo, sia per $T_{\mathcal{M}}(\cdot )$ che per $S_{\mathcal{M}}(\cdot )$:

• Caso pessimo: $T_{\mathcal{M}}(n)=\underset{x,|x|=n}{\max }{T}_{\mathcal{M}}(x)$
• Caso ottimo: $T_{\mathcal{M}}(n)=\underset{x,|x|=n}{\min }{T}_{\mathcal{M}}(x)$
• Caso medio: $T_{\mathcal{M}}(n)=\sum _{x,|x|=n}\text{Pr}(\mathcal{X}=x)T_{\mathcal{M}}(x)$

Introduciamo una notazione per indicare il comportamento asintotico di una funzione:

• Notazione $\mathcal{O}$-grande per il limite asintotico superiore
• Notazione $\Omega$-grande per il limite asintotico inferiore
• Notazione $\Theta$-grande per il limite asintotico sia superiore che inferiore

Notazione $\mathcal{O}$-grande

Note

Definiamo $\mathcal{O}(g(n))$ come l’insieme di funzioni $f(n)$ con dominio in $\mathbb{N}$:

$$\mathcal{O}(g(n))=\{f(n)\mid \exists c>0,n_0>0\text{ tali che }\forall n>n_{0}f(n)\le c\cdot g(n)\}$$

È comune usare $f(n)=\mathcal{O}(g(n))$ al posto di $f(n)\in \mathcal{O}(g(n))$ come abuso di notazione.

Se $\exists {\lim }_{n\to \infty }\frac{f(n)}{g(n)}=l$, allora $f(n)\in \mathcal{O}(g(n))$ se e solo se $l<+\infty$.

Notazione $\Omega$-grande

Note

Definiamo $\Omega (g(n))$ come l’insieme di funzioni $f(n)$ con dominio in $\mathbb{N}$: >

$$\Omega (g(n))=\{f(n)\mid \exists c>0,n_0>0\text{ tali che }\forall n>n_{0}f(n)\ge c\cdot g(n)\}$$

Si ha che se e solo se $f(n)\in \mathcal{O}(g(n))$ allora $g(n)\in \Omega (f(n))$.

Se $\exists {\lim }_{n\to \infty }\frac{f(n)}{g(n)}=l$, allora $f(n)\in \Omega (g(n))$ se e solo se $l>0$.

Notazione $\Theta$-grande

Note

Definiamo $\Theta (g(n))$ come l’insieme di funzioni $f(n)$ con dominio in $\mathbb{N}$: >

$$\Theta (g(n))=\{f(n)\mid \exists c_1>0,c_2>0n_0>0\text{ tali che }\forall n>n_0{c}_{1}g(n)\le f(n)\le c_2\cdot g(n)\}$$

Si ha che l’appartenenza a $\Theta (f(n))$ è una relazione di equivalenza sull’insieme di funzioni. Si ha che inoltre che $f(n)\in \Theta (g(n))$ se e solo se $f(n)\in \mathcal{O}(g(n))\wedge f(n)\in \Omega (g(n))$.

Se ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=c$ con $c\ne 0$ e $c\ne \infty$, allora $f(n)\in \Theta (g(n))$.

Tip

Spesso è necessario trovare un compromesso spazio-temporale per la risoluzione di un problema.

In generale si ha che:

• $S_{\mathcal{F}\mathcal{S}\mathcal{A}}(n)\in \Theta (1)$ e $T_{\mathcal{F}\mathcal{S}\mathcal{A}}\in \Theta (n)$
• $S_{\mathcal{A}\mathcal{DP}}(n)\in \mathcal{O}(n)$ e $T_{\mathcal{A}\mathcal{DP}}\in \Theta (n)$
• $S_{\mathcal{M}}(n)$ non potrà mai essere minore di $\Theta (n)$

Teoremi di accelerazione lineare

Note

Si ha che:

• Se $L$ è accettato da una MT $\mathcal{M}$ a $k$ nastri in $S_{\mathcal{M}}(n)$, per ogni $c\in \mathbb{Q},c>0$ posso costruire una MT ${\mathcal{M}}^{\prime }$ a $k$ nastri con $S_{{\mathcal{M}}^{\prime }}(n)<c\cdot S_{\mathcal{M}}(n)$
• Se $L$ è accettato da una MT $\mathcal{M}$ a $k$ nastri in $S_{\mathcal{M}}(n)$, posso costruire una MT ${\mathcal{M}}^{\prime }$ a $1$ nastro (non nastro singolo) con $S_{{\mathcal{M}}^{\prime }}(n)=S_{\mathcal{M}}(n)$
• Se $L$ è accettato da una MT $\mathcal{M}$ a $k$ nastri in $S_{\mathcal{M}}(n)$, per ogni $c\in \mathbb{Q},c>0$ posso costruire una MT ${\mathcal{M}}^{\prime }$ a $k=1$ nastri con $S_{{\mathcal{M}}^{\prime }}(n)<c\cdot S_{\mathcal{M}}(n)$
• Se $L$ è accettato da una MT $\mathcal{M}$ a $k$ nastri in $T_{\mathcal{M}}(n)$, per ogni $c\in \mathbb{Q},c>0$ posso costruire una MT ${\mathcal{M}}^{\prime }$ a $k+1$ nastri con $T_{{\mathcal{M}}^{\prime }}(n)=\max (n+1,c\cdot T_{\mathcal{M}}(n))$

Dimostrazione

Dimostriamo il primo teorema:

Scegliamo un fattore di compressione intero $r$ tale che $r\ge c$. Per ognuno degli $i$ nastri di $\mathcal{M}$, considero l’alfabeto ${\Gamma }_i$ e costruisco ${\Gamma }_i^{\prime }$ di ${\mathcal{M}}^{\prime }$ creando un elemento in ${\Gamma }_i^{\prime }$ per ogni $s\in {\Gamma }_i^r$. Costruiamo quindi l’OC di ${\mathcal{M}}^{\prime }$ in moto tale per cui:

• Calcoli con i nuovi simboli sui nastri emulando le mosse di $\mathcal{M}$ spostando le testine sui nastri di ${\mathcal{M}}^{\prime }$ ogni $r$ movimenti di $\mathcal{M}$
• Memorizzi la posizione della testina “all’interno” dei nuovi simboli degli alfabeti di nastro $\Gamma$, usando gli stati.

Dimostriamo il quarto teorema:

Usiamo un approccio simile a quello precedente: codifichiamo in modo compresso i simboli dell’alfabeto $\mathcal{M}$ e calcoliamo sui simboli compressi. Dobbiamo considerare che la compressione è fatta a runtime: il minimo costo per effettuare la compressione è lineare nel numero di simboli da comprimere.

Comprimendo $r$ simboli in uno, nel caso pessimo, possono servirmi $3$ mosse ${\mathcal{M}}^{\prime }$ per emularne $r+1$ di $\mathcal{M}$.

Macchina RAM

Note

La macchina RAM ha un nastro di lettura In e uno di scrittura Out come nella MT. Assumiamo il programma cablato nell’OC, così come la logica del program counter. La RAM è dotata di una memoria ad accesso a indirizzamento diretto $M[n]n\in \mathbb{N}$ al posto dei nastri di memoria: l’accesso non necessita di scorrimento delle celle. Le istruzioni di un programma usano come primo operando sorgente e come operando destinazione $M[0]$. Ogni cella contiene un intero $x\in \mathbb{N}$.

Definiamo L’instruction set e semantica pseudo-RTL:

Istruzione	Semantica
LOAD X	$M[0]\leftarrow M[X]$
LOAD= X	$M[0]\leftarrow X$
LOAD* X	$M[0]\leftarrow M[M[X]]$
STORE X	$M[x]\leftarrow M[0]$
STORE* X	$M[M[X]]\leftarrow M[0]$
ADD X	$M[0]\leftarrow M[0]+M[X]$
SUB X	$M[0]\leftarrow M[0]-M[X]$
MUL X	$M[0]\leftarrow M[0]\times M[X]$
DIV X	$M[0]\leftarrow M[0]÷M[x]$
HALT	$-$
READ X	$M[X]\leftarrow \text{In}$
READ* X	$M[M[X]]\leftarrow \text{In}$
WRITE X	$\text{Out}\leftarrow M[X]$
WRITE= X	$\text{Out}\leftarrow X$
WRITE* X	$\text{Out}\leftarrow M[M[X]]$
JUMP L	$\text{PC}\leftarrow L\text{ se }M[0]=0$
JZ L	$PC\leftarrow L$

Limite del criterio di costo

Note

Si ha che copiare/spostare/scrivere/leggere un intero $i$ costa tanto quanto il suo numero di cifre in base $b$: ${\log }_b(i)=\Theta (\log (i))$. Il costo delle operazioni aritmetico/logiche elementari dipende dall’operazione, definendo $d={\log }_2(i)$ si ha che:

• Le addizioni e sottrazioni al bit costano $\Theta (d)$
• Le moltiplicazioni, scolasticamente, costano $\Theta (d^2)$
• Le divisioni, scolasticamente, costano $\Theta (d^2)$

Le istruzioni JUMP e HALT sono a costo costante.

Tesi di correlazione polinomiale

Note

Risolvere lo stesso problema con macchine diverse può dare luogo a complessità diverse. In generale non esiste un modello migliore in assoluto.

Sotto “ragionevoli” ipotesi di criteri di costo, se un problema è risolvibile da $\mathcal{M}$ in $T_{\mathcal{M}}(n)$, allora è risolvibile da qualsiasi altro modello ${\mathcal{M}}^{\prime }$ in $T_{{\mathcal{M}}^{\prime }}=\pi (T_{\mathcal{M}}(n))$ dove $\pi (\cdot )$ è un opportuno polinomio.

Si ha che, per la MT a $k$ nastri e RAM:

• La MT impiega al più $\Theta (T_{\mathcal{R}\mathcal{A}\mathcal{M}}(n))$ per simulare una mossa della RAM
• Se la RAM ha complessità $T_{\mathcal{R}\mathcal{A}\mathcal{M}}(n)$, essa effettua al più $T_{\mathcal{R}\mathcal{A}\mathcal{M}}(n)$ mosse
• La simulazione completa della RAM da parte della MT costa al più $\Theta ((T_{\mathcal{R}\mathcal{A}\mathcal{M}}(n){)}^2)$, e quindi il legame tra $T_{\mathcal{R}\mathcal{A}\mathcal{M}}(n)$ e $T_{\mathcal{M}\mathcal{T}}(n)$ è polinomiale.