Il problema P vs NP

La teoria della complessità computazionale è una branca della Theoretical Computer Science incentrata sulla classificazione di problemi computazionali in base ad una nozione formale di “difficoltà”. Più nello specifico, la complessità di ciascun problema computazionale viene attribuita secondo una stima delle risorse (di tempo o di spazio) richieste dall’esecuzione di un programma che “risolve” tale problema. Due tra le classi di complessità più conosciute sono P ed NP, definite come le collezioni dei problemi risolubili in tempo polinomiale, rispettivamente, da una macchina di Turing deterministica e da una macchina di Turing non-deterministica. La relazione tra queste due classi costituisce oggi uno dei problemi aperti più interessanti della matematica: tanto una dimostrazione di P =/ NP quanto una di P = NP porterebbero ad una serie di implicazioni sia logiche che filosofiche. Lo scopo del seminario sarà proprio quello di analizzare il problema P vs NP nelle sue principali sfumature. Dopo una breve introduzione alla complessità computazionale, presenteremo le classi P ed NP formulando la congettura P =/ NP: analizzeremo quindi lo status logico e le implicazioni filosofiche di tale enunciato. Infine, passeremo in rassegna i principali approcci adottati nel tentativo di dimostrare la congettura, così come le varie introspezioni sulla complessità che tali studi hanno permesso di raggiungere.

Relatore

Gianluca Curzi (Università di Torino, Dipartimento di Informatica)

Docente di riferimento

Prof. Alessandro Aldini

Vincoli di partecipazione

il seminario è limitato alle coorti di studenti che non hanno lezione

Date

Luogo	Data	Orario	Crediti (CFU)
Palazzo Albani, via Viti 10	20 Dicembre 2017	11:00	0.125