|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-TeoremiDellaGerarchia History
Hide minor edits - Show changes to output
Changed line 28 from:
Per qualunque funzione spazio costruibile f:N-> to:
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)). Changed line 68 from:
Per qualunque funzione tempo costruibile f:N-> to:
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)).
Changed line 7 from:
%center% %sottotitolo% Appunti & Dimostrazioni del 19 Maggio to:
%center% %sottotitolo% Appunti & Dimostrazioni del 26 Maggio
Added lines 1-81:
(:title Informatica Teorica - Teoremi della gerarchia:)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Teoremi della gerarchia ::'''
%center% %sottotitolo% Appunti & Dimostrazioni del 19 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:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Una funzione f:N->N, dove f(n) è almeno O(logn), è chiamata '''spazio costruibile''' se la funzione che mappa la stringa 1'^n^' 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 1'^n^'.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Una funzione t:N->N, dove t(n) è almeno O(n*logn), è chiamata '''tempo costruibile''' se la funzione che mappa la stringa 1'^n^' 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 1'^n^'.
!!Teorema 1 - sulla gerarchia nello spazio
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Per qualunque funzione spazio costruibile f: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 2'^o(f(n))^') entro cui D deve dare una risposta. Perciò il decisore arriverà a uno stato finale solo se impiega al più 2'^f(n)^' iterazioni.
>>left bgcolor=#fbf3ff width=auto border='2px solid #cccccc' padding=5px<<
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 2'^f(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
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Per qualsiasi coppia di funzioni f'_1_',f'_2_':N->N, dove f'_1_'(n) è o(f'_2_'(n)) ed f'_2_' è spazio costruibile,
%center%Attach:IT-corolSC1a.gif
>><<
Grazie a questo corollario possiamo individuare diverse classi di spazio complessità. Ad esempio, possiamo dimostrare che una funzione n'^c^' è spazio costruibile per ogni numero naturale c. Quindi per ogni coppia di numeri naturali c'_1_'<c'_2_' possiamo dire che:
%center%Attach:IT-corolSC1b.gif
Con un minimo di sforzo aggiuntivo si può mostrare che n'^c^' è spazio costruibile anche per ogni numero razionale c>0.
Se osserviamo che tra due numeri razionali c'_1_' e c'_2_' si possono sempre trovare due numeri reali e'_1_'<e'_2_' tali che e'_1_'<c'_1_'<c'_2_'<e'_2_', otteniamo un secondo corollario al teorema 1 che introduce una nuova gerarchia all'interno della classe PSPACE.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Per qualsiasi coppia di numeri reali 0≤e'_1_'≤e'_2_',
%center%Attach:IT-corolSC2.gif
>><<
!!Teorema 2 - sulla gerarchia nel tempo
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Per qualunque funzione tempo costruibile f: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
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Per qualsiasi coppia di funzioni t'_1_',t'_2_':N->N, dove t'_1_'(n) è o(t'_2_'(n))/log t'_2_'(n)) e t'_2_' è tempo costruibile,
%center%Attach:IT-corolTC.gif
>><<
Del Teorema 2 e rispettivo corollario non sono richieste dimostrazioni.\\
Andate in pace.
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
