Dipartimento di Scienze Statistiche

Il prof. Massimo Lauria terrà un seminario dal titolo: "LA COMPLESSITÀ COMPUTAZIONALE DELLE DIMOSTRAZIONI E DEGLI ALGORITMI" Abstract: L'area di ricerca "proof complexity" studia la complessità computazionale del dimostrare affermazioni logiche, in particolare di quanto debba essere lunga la dimostrazione di un'affermazione rispetto alla lunghezza dell'affermazione stessa. Risultati in quest'area hanno applicazioni nello studio degli algoritmi: è possibile studiare le performance di alcuni algoritmi interpretando la loro esecuzione come fosse una dimostrazione. Nel seminario introdurremo l'area della proof complexity, e vedremo come si collega allo studio degli algoritmi.