Il trilemma del segugio: Crisippo nel terzo millennio

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 decimo 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.
Questo seminario delineerà le nozioni centrali all’ambito della complessità computazionale, per poi approfondire il significato dell’NP-completezza. Esporrà alcuni problemi emblematici della famiglia NP, spiegherà in che senso ciascuno sia riconducibile agli altri. Esaminando uno dei più 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.

La registrazione del seminario è disponibile su YouTube.

Relatore

Eugenio Omodeo (Università di Trieste)

Docente di riferimento

Alessandro Aldini

Vincoli di partecipazione

Il seminario è aperto agli studenti del terzo anno e fuori corso, e si svolgerà in maniera interamente telematica. Ogni studente interessato a partecipare dovrà collegarsi, con nome e cognome, al link che verrà comunicato via mailing list.

Date

Luogo Data Orario Crediti (CFU)
ZOOM 25 Maggio 2021 10:30-12:30 0.125