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 di , la complessità temporale di è se si ferma in un dato , altrimenti. La complessità spaziale è definita come con lunghezza del contenuto del -esimo nastro alla mossa -esima, cioè la somma delle quantità di nastro occupate, per ogni nastro.

Sotto opportune ipotesi, è possibile semplificare da e a e , dove è la lunghezza dell’input. Generalmente scegliamo, sia per che per :

• Caso pessimo:
• Caso ottimo:
• Caso medio:

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

• Notazione -grande per il limite asintotico superiore
• Notazione -grande per il limite asintotico inferiore
• Notazione -grande per il limite asintotico sia superiore che inferiore

Notazione -grande

Note

Definiamo come l’insieme di funzioni con dominio in :

È comune usare al posto di come abuso di notazione.

Se , allora se e solo se .

Notazione -grande

Note

Definiamo come l’insieme di funzioni con dominio in : >

Si ha che se e solo se allora .

Se , allora se e solo se .

Notazione -grande

Note

Definiamo come l’insieme di funzioni con dominio in : >

Si ha che l’appartenenza a è una relazione di equivalenza sull’insieme di funzioni. Si ha che inoltre che se e solo se .

Se con e , allora .

Tip

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

In generale si ha che:

• e
• e
• non potrà mai essere minore di

Teoremi di accelerazione lineare

Note

Si ha che:

• Se è accettato da una MT a nastri in , per ogni posso costruire una MT a nastri con
• Se è accettato da una MT a nastri in , posso costruire una MT a nastro (non nastro singolo) con
• Se è accettato da una MT a nastri in , per ogni posso costruire una MT a nastri con
• Se è accettato da una MT a nastri in , per ogni posso costruire una MT a nastri con

Dimostrazione

Dimostriamo il primo teorema:

Scegliamo un fattore di compressione intero tale che . Per ognuno degli nastri di , considero l’alfabeto e costruisco di creando un elemento in per ogni . Costruiamo quindi l’OC di in moto tale per cui:

• Calcoli con i nuovi simboli sui nastri emulando le mosse di spostando le testine sui nastri di ogni movimenti di
• Memorizzi la posizione della testina “all’interno” dei nuovi simboli degli alfabeti di nastro , usando gli stati.

Dimostriamo il quarto teorema:

Usiamo un approccio simile a quello precedente: codifichiamo in modo compresso i simboli dell’alfabeto 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 simboli in uno, nel caso pessimo, possono servirmi mosse per emularne di .

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 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 . Ogni cella contiene un intero .

Definiamo L’instruction set e semantica pseudo-RTL:

Istruzione	Semantica
LOAD X
LOAD= X
LOAD* X
STORE X
STORE* X
ADD X
SUB X
MUL X
DIV X
HALT
READ X
READ* X
WRITE X
WRITE= X
WRITE* X
JUMP L
JZ L

Limite del criterio di costo

Note

Si ha che copiare/spostare/scrivere/leggere un intero costa tanto quanto il suo numero di cifre in base : . Il costo delle operazioni aritmetico/logiche elementari dipende dall’operazione, definendo si ha che:

• Le addizioni e sottrazioni al bit costano
• Le moltiplicazioni, scolasticamente, costano
• Le divisioni, scolasticamente, costano

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 in , allora è risolvibile da qualsiasi altro modello in dove è un opportuno polinomio.

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

• La MT impiega al più per simulare una mossa della RAM
• Se la RAM ha complessità , essa effettua al più mosse
• La simulazione completa della RAM da parte della MT costa al più , e quindi il legame tra e è polinomiale.