BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Descriptive Complexity - Felipe Ferreira Santos
DTSTART:20210305T110000Z
DTEND:20210305T120000Z
UID:TALK157720@talks.cam.ac.uk
CONTACT:Nathanael Arkor
DESCRIPTION:Descriptive complexity is the branch of computational complexi
 ty theory that attempts to characterize complexity classes in terms of the
  logics that capture them. We begin by formally defining what it means for
  a logic to capture a complexity class. We then define existential second-
 order logic and give an outline for the proof of Fagin's theorem\, which s
 tates that existential second-order logic captures NP. In reference to the
  P vs NP problem\, we follow by surveying different attempts to define a l
 ogic which captures P. We conclude by stating Gurevich's conjecture\, whic
 h asserts no logic captures P. Clearly\, the conjecture immediately implie
 s P is not equal to NP.
LOCATION:https://meet.google.com/jxy-edcv-wgx
END:VEVENT
END:VCALENDAR