Lecture by Bruce Kapron, University of Victoria, Canada
Date: 08 FEBRUARY 2022 from 17:30 to 19:00
Event location: Sala Rossa, Palazzo Marchesini, Via Marsala, 26 - Bologna - In presence and online event
Type: Lectures
The year 1971 marked a turning point in the study of theoretical computer science, with the appearance of the paper "The Complexity of Theorem-proving Procedures" by Stephen A. Cook. In current terminology, this paper introduced the notion of NP-completeness, which has become a central notion in the study of computational difficulty, allowing a characterization of problems that are the most difficult among those whose solutions may be efficiently verified. This work is of theoretical and practical significance, allowing for a more rigorous approach to algorithmic problem-solving, as well as posing one of the most challenging mathematical problems of our day -- the "P vs NP" problem. In this talk I will present the basic ideas underlying Cook's work, and survey the impact it has had in computer science and mathematics, as well as its broader impact in areas from economics to philosophy.
Link to ZOOM: Click here to access
If you prefer to attend this lecture in presence, you should write to segreteria.isa@unibo.it within February 8th, 12 p.m. and book your place. The places will be assigned on “first come first served” basis.
In order to attend lectures in presence you must have a COVID-19 Green Pass and show it on the premises.
In-presence attendance is allowed for academic stakeholders only.
The visit of Bruce Kapron is organized in collaboration with Ugo Dal Lago from the Department of Computer Science and Engineering.