Luca Mariot è assistant professor all’università di Twente nei Paesi Bassi, si occupa di crittografia e sicurezza informatica. Con Luca abbiamo discusso della teoria della complessità computazionale.

La teoria della complessità computazionale, ’ complexity theory è la branca dell'informatica e della matematica che studia quante risorse (come tempo o memoria) sono necessarie per risolvere un problema computazionale. In altre parole, non si chiede solo se un problema possa essere risolto (che è ciò che la teoria della computabilità esamina), ma anche con quale efficienza possa essere risolto, un problema che è stato affrontato dai tempi di Turing e Gödel. La teoria della complessità ci fornisce una mappa del panorama dei problemi: cosa è facile, cosa è difficile e cosa sta nel mezzo. Non plasma solo la nostra comprensione dei computer, ma plasma anche la nostra comprensione del ragionamento, dell'intelligenza, della scienza e persino della realtà stessa.

Link utili
- Una panoramica sulla teoria della complessità computazionale: https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
- Un saggio esaustivo su complexity theory e implicazioni filosofico-scientifiche: https://www.scottaaronson.com/papers/philos.pdf