Seminario
Il trilemma del segugio: Crisippo nel terzo millennio
Programma
Uno dei sette problemi per il millennio proposti dal Clay Mathematics Institute nell'anno 2000 è noto con la sigla “P vs NP”. Esso presenta una contiguità concettuale con il decimo dei 23 problemi che Hilbert proponeva, nell'anno 1900, come sfide per la matematica del XX secolo. Per poter dare risposta al 10° problema di Hilbert occorreva esplicitare la nozione di algoritmo e dunque sviluppare una teoria della computabilità; da questa, con l’evolversi della tecnologia, si è diramato lo studio della complessità computazionale che si domanda: “quanto tempo di calcolo e quanta memoria richiede la risoluzione di ciascun’istanza di un certo problema?” Non di rado un algoritmo è atto alla risoluzione di un problema ma solo in linea di principio, in quanto esso richiede in qualche caso tempi di calcolo proibitivi; da ciò scaturisce la questione: “quali, fra i problemi algoritmicamente risolubili, sono davvero trattabili ?” C’è una pervasiva famiglia di problemi, detti NP-completi, dei quali ancor oggi non siamo in grado di dire se siano risolubili tramite algoritmi di complessità polinomiale. Sappiamo nondimeno che se uno di essi si rivelasse - in questa ben poco esigente accezione del termine - trattabile, tali allora risulterebbero anche tutti gli altri. Questa conferenza delineerà le nozioni centrali all’ambito della complessita? computazionale, per poi approfondire il significato della NP-completezza. Esporrà alcuni problemi emblematici della famiglia NP, spiegherà in che senso ciascuno sia riconducibile agli altri. Esaminando uno dei piu? rappresentativi problemi di questa famiglia, quello di stabilire se un enunciato proposizionale sia soddisfacibile o meno, chiarirà infine perché la sua risoluzione sembri esigere —allo stato odierno delle nostre conoscenze— un sia pur occasionale ricorso alla forza bruta.
Online via ZOOM: https://uniurb-it.zoom.us/j/81705024027?pwd=d3pxZFFSNzZqWWIyYVo1MVRSK0Fndz09
Relatori/Relatrici
Eugenio Omodeo (Università di Trieste)
Dettagli sull'evento
Data e luogo
Inizio: 25/05/2021
alle ore 10:30
Fine: 25/05/2021
alle ore 12:30
Online
Organizzato e promosso da:
Dipartimento di Scienze Pure e Applicate
Synergia Research Group
Modalità di partecipazione
Altre informazioni utili
Per informazioni contattare pierluigi.graziani@uniurb.it
