Question

Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here:

Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?"

My question is, has there been any work done to tackle the P versus NP problem from this logical angle, by reasoning about existential second-order logic and first-order logic with least fixed point?

And more generally, what are some good references for learning about least fixed point logic?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top