Abstract

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.