University of Cambridge > > Logic & Semantics for Dummies > Descriptive Complexity

Descriptive Complexity

Add to your list(s) Download to your calendar using vCal

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity