• Autore:   Elia Argentieri
  • Ultima modifica:   6 mag 2022 18:07
  • Redazione:   3 feb 2022 17:55
  • Sorgente di questa pagina
  • Tempo di lettura:   6 minuti

Oggi studiamo le funzioni di misura, cioè quelle funzioni che abbiamo utilizzato per limitare la quantità di risorse che una macchina può impiegare per risolvere un problema. Abbiamo usato funzioni che stimano il numero di passi e funzioni che stimano il numero di celle necessarie a memorizzare un dato.

In principio una funzione di misura può essere una qualunque funzione totale f : ℕ ↦ ℕ e può anche avere una complessità enorme. Funzioni di misura arbitrarie possono portare a risultati quantomeno controintuitivi e sorprendenti, come vedremo più avanti.

Per questo motivo introduciamo alcune funzioni di misura, dette appropiate, che hanno una complessità a loro volta limitata: per esempio l’algoritmo che calcola f(x) deve richiedere tempo \(\mathcal{O}(f(|x|) + |x|)\) (l’addendo |x| fa si che la complessità sia almeno lineare, infatti f porebbe essere sub-lineare) e spazio \(\mathcal{O}(f(x))\) .

Definizione: la funzione \(f : \mathbb{N} \mapsto \mathbb{N}\) calcolabile totale è appropiata se:

  1. è monotona crescente
  2. esiste una MdT M a k nastri, tale che \(\forall x \in \Sigma^\star\) si arresta in tempo \(\mathcal{O}(f(|x|) + |x|)\) e in spazio \(\mathcal{O}(f(|x|))\) e restituisce come risultato \(f(|x|)\) codificato in base 1 con \(\diamond \notin \Sigma\) simbolo speciale, cioè lascia sul nastro \(\diamond^{f(|x|)}\) .

Esempi di funzioni appropiate: \(k, n, n^k, k^n, n!, \lfloor \log n \rfloor, \lfloor \sqrt n \rfloor\) , inoltre se f e g sono appropiate lo sono anche f + g e f × g, quindi tutti i polinomi sono funzioni appropiate e per finire pure \(f^g\) e \(g \circ f\) lo sono.

Gerarchia di tempo e spazio

Enunciamo senza dimostrarlo accuratamente, un teorema che ci assicura circa l’esistenza di una gerarchia di classi di complessità in tempo e spazio.

Teorema: se f è appropiata, allora:

  • \(\mathrm{TIME}(f(n)) \subsetneq \mathrm{TIME}((f(2n + 1))^3)\)
  • \(\mathrm{SPACE}(f(n)) \subsetneq \mathrm{SPACE}(f(n) \times \log f(n))\)

La dimostrazione del primo punto si basa sulla diagonalizzazione:

$$\{x | \varphi_x(x) \text{ converge entro } f(|x|) \text{ passi}\} \in \mathrm{TIME}(f^3) \text{, ma non appartiene a } \mathrm{TIME}(f)$$

La dimostrazione del secondo punto è analoga.

Classe dei problemi decidibili in tempo esponenziale deterministico

Introduciamo un’altra classe di complessità in tempo che utilizziamo subito per dimostrare un corollario del teorema di gerarchia precedente.

Definizione:

$$\mathrm{EXP} = \bigcup_{k \geq 1} \mathrm{TIME}(2^{n^k})$$

Corollario:

$$\mathcal{P} \subsetneq \mathrm{EXP}$$

Dimostrazione: l’inclusione è ovvia perché \(2^n\) cresce più velocemente di ogni polinomio; è propria perché

$$\mathcal{P} \subseteq \mathrm{TIME}(2^n) \subsetneq \mathrm{TIME}((2^{(2n + 1)})^3) \subseteq \mathrm{TIME}(2^{n^2})$$

Questo corollario, insieme al fatto che \(\mathrm{TIME}(f(n)) \subseteq \mathrm{TIME}(c^{f(n)})\) , ci permette di concludere che \(\mathcal{NP} \subset \mathrm{EXP}\) . Questa inclusione giustifica il metodi di forza bruta, perché in tempo deterministico esponenziale genera tutti i candidati e poi certifica che un candidato è una soluzione in tempo deterministico polinomiale.

Espandiamo la gerarchia, senza dimostrare:

Teorema: siano f una funzione di misura appropiata e k una costante, allora:

  • \(\mathrm{SPACE}(f(n)) \subseteq \mathrm{NSPACE}(f(n))\)
  • \(\mathrm{TIME}(f(n)) \subseteq \mathrm{NTIME}(f(n))\)
  • \(\mathrm{NSPACE}(f(n)) \subseteq \mathrm{TIME}(k^{\log n + f(n)})\)

Ricordiamo che avevamo già stabilito questi fatti:

  • \(\mathrm{LOGSPACE} \subseteq \mathcal{P}\)
  • \(\mathrm{LOGSPACE} \subsetneq \mathrm{PSPACE}\)
  • \(\mathrm{PSPACE} = \mathrm{NPSPACE}\)
  • \(\mathcal{NP} \subseteq \mathrm{EXP}\)

Osserviamo che la gerarchia non è superiormente limitata: esistono problemi arbitrariamente difficili, indipendentemente dagli algoritmi usati.

Teorema: per ogni funzione calcolabile totale g esiste un problema \(I \in \mathrm{TIME}(f(n))\) e \(I \notin \mathrm{TIME}(g(n))\) con \(f(n) > g(n)\) quasi ovunque.

Da notare il fatto che questo teorema non richieda che le funzioni di misura siano appropiate. Questo fatto ci spingerebbe a abbandonare anche per i teoremi precedenti, i requisiti imposti sulle funzioni appropiate.

Abbandonando le funzioni appropiate

Se ignoriamo la definizione di funzione appropiata, possiamo dimostrare una serie di teoremi controintuitivi.

Il primo che vediamo, senza dimostrarlo è il teorema di accelerazione di Blum.

Teorema di accelerazione di Blum

Una parte molto importante dell’informatica riguarda la ricerca e lo studio di algoritmi ottimi per risolvere un dato problema, ovvero algoritmi le cui prestazioni non possono essere migliorate se non per una costante moltiplicativa.

Vediamo adesso questo teorema che ci lascia con un risultato negativo: non sempre esiste un algoritmo ottimo. Si può affermare che esistono programmi che sono più veloci su una macchina vecchia e lenta che su una macchina nuova e veloce.

Teorema: per ogni funzione calcolabile totale h, esiste un problema I tale che, per ogni algoritmo M che decide I in tempo f, esiste M’ che decide I in tempo f’ tale che>:

$$f(n) > h(f'(n)) \text{ quasi ovunque}$$

Sappiamo già che ogni funzione calcolabile ha un numero infinito numerabile di programmi differenti che la calcolano. Nella teoria degli algoritmi spesso si vuole trovare l’algoritmo con la complessità più piccola per una certa funzione calcolabile e una certa misura di complessità (si cerca l’algoritmo ottimo). Se non pongo restrizioni sulla funzione di misura della complessità, quel che succede è che posso trovare funzioni calcolabili che non ammettono un algoritmo ottimo rispetto a quella misura. In altre parole possiamo dimostrare l’esistenza di una successione di algoritmi via via più efficienti per risolvere il problema costruito in funzione di h. Comunque il teorema non esclude la possibilità di trovare algoritmi ottimi rispetto a certe funzioni specifiche, solo che non posso trovarlo per tutte le funzioni.

Teorema della lacuna di Borodin

Senza usare funzioni appropiate, scopriamo anche che all’aumentare delle risorse di calcolo non si allarga la classe dei problemi decisi con esse. Si contraddice l’idea intuitiva che ci debba essere una gerarchia di classi di complessità.

L’enunciato qui proposto è una forma speciale del teorema generale: invece di considerare una generica funzione calcolabile h, fissiamo la funzione \(2^n\) . Il risultato è che non si trova alcun problema decidibile in tempo deterministico strettamente superiore a f(n) e strettamente inferiore a \(2^{f(n)}\) .

Teorema: esiste f calcolabile totale (monotona) tale che:

$$\mathrm{TIME}(f(n)) = \mathrm{TIME}(2^{f(n)})$$

La funzione f definita dal teorema non è una funzione appropiata e infatti cresce estremamente rapidamente, il che è proibito dalle funzioni appropiate.

Di questi teoremi (di accelerazione e della lacuna) esiste anche la versione di complessità in spazio.

Assiomi di Blum

Vediamo un’altra caratterizzazione alternativa alle funzioni appropiate: le funzioni di misura di Blum, che si basano su 2 soli assiomi, indipendenti dal modello di calcolo.

Definizione: una funzione ϕ è una misura di complessità se restituisce un naturale a fronte di una funzione ψ e del suo ingresso x e inoltre soddisfa i seguenti assiomi:

  1. \(\phi(\psi,x)\) è definita se e solo se \(\psi(x)\) lo è
  2. per ogni \(\psi, x, k\) è decidibile se \(\phi(\psi,x) = k\)

Il primo assioma ci dice che ϕ misura la complessità del calcolo di ψ(x); il secondo assicura che si può davvero ottenere la complessità del calcolo di ψ(x). Quindi se la funzione ϕ misurasse il numero di passi, otterremmo la vecchia definizione di complessità in tempo; se misurasse le celle toccate, quella in spazio.

Le funzioni appropiate soddisfano entrambi gli assiomi, tuttavia ci sono funzioni di misura di Blum che soddisfano tali assiomi, ma il cui impiego porta a risultati, ancora una volta sorprendenti. Per esempio può capitare che la complessità di due algoritmi composti in sequenza, risulti minore della complessità del primo dei due, cioè fare altri calcoli riduce la complessità del problema appena risolto!

Di conseguenza le funzioni appropiate sono quelle più sensate da usare.