COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Descriptive ComplexityAdd to your list(s) Download to your calendar using vCal - Felipe Ferreira Santos
- Friday 05 March 2021, 11:00-12:00
- https://meet.google.com/jxy-edcv-wgx.
If you have a question about this talk, please contact Nathanael Arkor. Descriptive complexity is the branch of computational complexity 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 states that existential second-order logic captures NP. In reference to the P vs NP problem, we follow by surveying different attempts to define a logic which captures P. We conclude by stating Gurevich’s conjecture, which asserts no logic captures P. Clearly, the conjecture immediately implies P is not equal to NP. This talk is part of the Logic & Semantics for Dummies series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsEfficient and intuitive modelling of electromagnetic nanoresonators and complex metasurfaces Is Water H20? Exam Mock Up Test## Other talksHuman driving, vehicle dynamics and machine learning Wolfson Arts - Representation as a Matter of Fact (Professor Phillip Lindley in conversation with Amikam Toren) Family-based study of Autism Spectrum Disorders Dwarf galaxies beyond supernova feedback: galaxy formation with radiation, magnetic fields, and cosmic rays Non-canonical cross-presentation: what is it and when does it work?” |