cerca
Informatica Teorica - Teoremi della gerarchia
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Informatica Teorica - Teoremi della gerarchia

Torna alla pagina di Informatica Teorica


 :: Informatica Teorica - Teoremi della gerarchia ::

Appunti & Dimostrazioni del 26 Maggio

Teoremi della gerarchia

I teoremi della gerarchia confermano una banale intuizione: più tempo e spazio hanno a disposizione le MdT, e più il numero dei problemi che riescono a risolvere aumenta. Si parla di "gerarchie" perché questi teoremi dimostrano che non tutte le classi di tempo e spazio complessità sono uguali, ma alcune sono più ampie di altre.

Diamo due definizioni, rispettivamente nello spazio e nel tempo:

Una funzione f:N->N, dove f(n) è almeno O(logn), è chiamata spazio costruibile se la funzione che mappa la stringa 1n alla rappresentazione binaria di f(n) è computabile in O(f(n)) spazio.

Ciò significa che f è spazio costruibile se esiste una MdT M di spazio O(f(n)) che termina sempre con la rappresentazione binaria di f(n) quando ha in input una stringa 1n.

Una funzione t:N->N, dove t(n) è almeno O(n*logn), è chiamata tempo costruibile se la funzione che mappa la stringa 1n alla rappresentazione binaria di t(n) è computabile in tempo O(t(n)).

Similmente a prima, la funzione t è tempo costruibile se esiste una MdT M di tempo O(t(n)) che termina sempre con la rappresentazione binaria di t(n) quando ha in input una stringa 1n.

Teorema 1 - sulla gerarchia nello spazio

Per qualunque funzione spazio costruibile f:N->N, esiste un linguaggio A decidibile in uno spazio O(f(n)) ma non in uno spazio o(f(n)).

Cenni di dimostrazione

Per la nostra dimostrazione introdurremo un algoritmo D che decide il linguaggio A in O(f(n)) spazio, e un algoritmo M che decide un qualsiasi linguaggio B in o(f(n)) spazio. Il decisore D dovrà essere perciò costruito in modo da garantire che A sia diverso da un qualunque B. Vediamo come.

Ad entrambi i decisori viene dato in pasto lo stesso ingresso, che consiste nella descrizione di M seguita da un 1 e da un certo numero di 0, ovvero: w=<M>10*. In linea di principio, se M riesce a terminare entro il limite di spazio o(f(n)), allora D deve rifiutare per rimarcare il fatto che accetta linguaggi differenti dall'altro; e viceversa. La prima cosa che dovrà fare D sarà quindi calcolare lo spazio all'interno del quale risolvere il problema, poi verificare che l'ingresso w sia nel formato corretto, e infine fare il running di M. Ultimo accorgimento: poiché D è un decisore bisogna dare garanzia che termini, ma dato che M potrebbe andare in loop fissiamo un numero massimo di passi (proporzionale a 2o(f(n))) entro cui D deve dare una risposta. Perciò il decisore arriverà a uno stato finale solo se impiega al più 2f(n) iterazioni.

D = "su ingresso w:

  1. sia n la lunghezza di w;
  2. calcola f(n) usando spazio-costruibilità. Se nei passi successivi si usa spazio maggiore di quello calcolato, allora RIFIUTA (perché stiamo andando oltre il limite consentito);
  3. se w non è nella forma <M>10* per una MdT M, allora RIFIUTA;
  4. simula M su w e conta il numero di passi. Se il contatore è maggiore di 2f(n), allora RIFIUTA (perché stiamo andando in loop);
  5. se M accetta, allora RIFIUTA; altrimenti ACCETTA."

Per grazia ricevuta (dalla Trucco), possiamo affermare senza ulteriori dimostrazioni o spiegazioni che l'algoritmo appena descritto ci garantisce che se il linguaggio è riconosciuto in O(f(n)) allora non lo è in o(f(n)), dimostrando così il teorema.

Corollari al Teorema 1

Per qualsiasi coppia di funzioni f1,f2:N->N, dove f1(n) è o(f2(n)) ed f2 è spazio costruibile,

Grazie a questo corollario possiamo individuare diverse classi di spazio complessità. Ad esempio, possiamo dimostrare che una funzione nc è spazio costruibile per ogni numero naturale c. Quindi per ogni coppia di numeri naturali c1<c2 possiamo dire che:

Con un minimo di sforzo aggiuntivo si può mostrare che nc è spazio costruibile anche per ogni numero razionale c>0.

Se osserviamo che tra due numeri razionali c1 e c2 si possono sempre trovare due numeri reali e1<e2 tali che e1<c1<c2<e2, otteniamo un secondo corollario al teorema 1 che introduce una nuova gerarchia all'interno della classe PSPACE.

Per qualsiasi coppia di numeri reali 0≤e1≤e2,

Teorema 2 - sulla gerarchia nel tempo

Per qualunque funzione tempo costruibile f:N->N, esiste un linguaggio A decidibile in un tempo O(t(n)) ma non in uno spazio o(t(n)/log t(n)).

Corollario al Teorema 2

Per qualsiasi coppia di funzioni t1,t2:N->N, dove t1(n) è o(t2(n))/log t2(n)) e t2 è tempo costruibile,

Del Teorema 2 e rispettivo corollario non sono richieste dimostrazioni.
Andate in pace.


Torna alla pagina di Informatica Teorica