Descriptive Complexity

Add 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:

• Logic & Semantics for Dummies
• https://meet.google.com/jxy-edcv-wgx
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.