b"\n_START_ARTICLE_\nCompromesso tempo-memoria\n_START_PARAGRAPH_\nIn informatica il compromesso tempo-memoria (o compromesso spazio-tempo) \xc3\xa8 una situazione dove l'utilizzo della memoria pu\xc3\xb2 essere ridotto al prezzo di un rallentamento della velocit\xc3\xa0 di esecuzione del programma o, viceversa, il tempo di calcolo pu\xc3\xb2 essere ridotto al prezzo di un incremento dell'utilizzo della memoria. Al variare dei relativi costi di cicli di CPU, spazio RAM e spazio su disco rigido possono cambiare radicalmente le scelte per i compromessi tempo-memoria. Spesso, approntare un compromesso tempo-memoria pu\xc3\xb2 portare un programma ad essere eseguito molto pi\xc3\xb9 velocemente.\n_START_SECTION_\nApplicazioni in campo informatico\n_START_PARAGRAPH_\nLa situazione pi\xc3\xb9 comune \xc3\xa8 un algoritmo che opera su una tabella di associazione: una implementazione pu\xc3\xb2 includere l'intera tabella, cosa che riduce il tempo di calcolo ma incrementa la quantit\xc3\xa0 di memoria necessaria; un'altra implementazione pu\xc3\xb2 calcolare la tabella al momento, cosa che incrementa il tempo di calcolo ma riduce la quantit\xc3\xa0 di memoria necessaria._NEWLINE_Un compromesso spazio-tempo pu\xc3\xb2 essere applicato al problema della memorizzazione dei dati. Se i dati sono memorizzati in forma non compressa possono prendere molto spazio ma richiedono meno tempo per essere letti rispetto a dati memorizzati in forma compressa (questo a causa del fatto che la compressione dei dati riduce lo spazio richiesto per la loro archiviazione ma richiede del tempo per eseguire l'algoritmo di compressione). A seconda delle necessit\xc3\xa0 pu\xc3\xb2 essere utile l'una oppure l'altra soluzione. Un altro esempio \xc3\xa8 la visualizzazione di formule matematiche su siti web con informazioni prevalentemente in formato testuale come ad esempio la Wikipedia stessa. La memorizzazione del solo sorgente LaTex ed il rendering come immagine solo al momento in cui la pagina \xc3\xa8 richiesta \xc3\xa8 un processo che permette di risparmiare spazio su disco ma comporta pi\xc3\xb9 tempo per la visualizzazione. L'altra soluzione \xc3\xa8 di renderizzare l'immagine quando la pagina viene modificata e di memorizzarla su disco per caricarla al momento della visualizzazione della pagina. Questa soluzione comporta un consumo maggiore di spazio su disco ma un tempo minore per l'accesso ai dati. \xc3\x88 doveroso precisare che ci sono rare situazioni in cui \xc3\xa8 possibile lavorare direttamente con i dati compressi, come nel caso di indici di immagini compresse dove \xc3\xa8 pi\xc3\xb9 rapido lavorare con la compressione che senza di essa.\n_START_SECTION_\nApplicazioni in campo crittografico\n_START_PARAGRAPH_\nIn campo crittografico, dove un attaccante cerca di violare un cifrario con qualunque tecnica che gli consenta risultati migliori di quelli ottenibili applicando la semplice forza bruta, i vantaggi di un compromesso tempo-memoria sono chiaramente visibili._NEWLINE_La prima applicazione del compromesso tempo-memoria in questo ambito \xc3\xa8 ad opera di Martin Hellman che nel 1980 dimostr\xc3\xb2 come l'uso di tabelle precompilate per la ricerca delle possibili chiavi segrete dei cifrari a blocchi distribuisse lo spazio delle possibili chiavi tra la memoria ed il tempo di calcolo. Questo metodo crittanalitico fu poi applicato ai cifrari a flusso da Alex Biryukov ed Adi Shamir considerando anche di conoscere i dati in output. Recentemente Philippe Oechslin ha pubblicato una versione migliorata dell'idea originale di Hellman grazie alla quale il tempo computazionale si riduce ulteriormente utilizzando le tabelle arcobaleno. Oechslin ha utilizzato la sua tecnica anche come metodo per il recupero delle password del sistema operativo Microsoft Windows._NEWLINE_Le tabelle arcobaleno sono particolari tabelle di associazione che utilizzano hash precompilati da una funzione crittografica di hash per violare le chiavi segrete in minuti invece che in settimane o mesi. Riducendo la dimensione della tabella arcobaleno si incrementa il tempo richiesto per iterare su tutti gli hash possibili. L'attacco Meet-in-the-middle usa un compromesso tempo-memoria per trovare la chiave crittografica con sole 2n + 1 cifrature (ed uno spazio di O(2n)) contro le 22n cifratura stimate (ma con uno spazio di soli O(1)) di un attacco semplice."