BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic &\; Semantics for Dummies
SUMMARY:Descriptive Complexity - Felipe Ferreira Santos
DTSTART;TZID=Europe/London:20210305T110000
DTEND;TZID=Europe/London:20210305T120000
UID:TALK157720AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/157720
DESCRIPTION:Descriptive complexity is the branch of computatio
nal complexity theory that attempts to characteriz
e complexity classes in terms of the logics that c
apture 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 states that existential second-order logic
captures NP. In reference to the P vs NP problem\,
we follow by surveying different attempts to defi
ne a logic which captures P. We conclude by statin
g Gurevich's conjecture\, which asserts no logic c
aptures P. Clearly\, the conjecture immediately im
plies P is not equal to NP.
LOCATION:https://meet.google.com/jxy-edcv-wgx
CONTACT:Nathanael Arkor
END:VEVENT
END:VCALENDAR