Un viaggio dentro ICC

Relatore
Margherita Zorzi - Università degli Studi di Verona
Data e ora
martedì 16 marzo 2010 alle ore 16.45 - Ore 16.45 caffe' e pasticcini, ore 17 inizio seminario
Luogo
Ca' Vignal - Piramide, Piano 0, Sala Verde
Referente
Referente esterno
Data pubblicazione
4 marzo 2010
Dipartimento
 

Riassunto

 In questo seminario presenterò le principali tecniche utilizzate in Complessità Computazionale Implicita (ICC).
La ICC è un approccio alla complessità computazionale caratterizzato dell'essere indipendente dai modelli di calcolo (Macchine di Turing, Famiglie di Circuiti...). In ICC si utilizzano diverse tecniche: dalla limitazione dello schema di ricorsione o dell'aritmetica, fino all'utilizzo delle "logiche leggere".
Durante la discussione illustrerò i principi di base di diversi approcci ICC e mi soffermerò infine su un recente lavoro che ha generalizzato la tired recursion (tecnica di ricorsione in grado di catturare le funzioni polytime sviluppata per le word algebras da D. Leivant nei primi anni Novanta) estendendola a tutte le free algebras.






© 2002 - 2021  Universit√† degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234