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:
- sia n la lunghezza di w;
- 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);
- se w non è nella forma <M>10* per una MdT M, allora RIFIUTA;
- simula M su w e conta il numero di passi. Se il contatore è maggiore di 2f(n), allora RIFIUTA (perché stiamo andando in loop);
- 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
