4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Please ask only one question per post. For your first question, Wikipedia gives a reference to a paper ([52]). Have you tried reading it, and the papers it cites? It seems to cite some papers in the literature that discuss this subject. Have you tried reading them? Have you tried finding Google Scholar to find other papers that cite it? $\endgroup$ – D.W. Jul 26 '18 at 1:15
  • 2
    $\begingroup$ For your second question, requests for book recommendations generally don't work well here. To make them work well they must have a set of clearly defined criteria. You should show us what books you've already considered and why you rejected them or what research you've done. Currently the only criteria you give is "good", but "good" is a matter of opinion and so not a good fit for this site (see our help center). $\endgroup$ – D.W. Jul 26 '18 at 1:16
3
+50
$\begingroup$

Your second question first. The context of your question is called descriptive complexity theory. In this context, I would suggest the book Finite Model Theory by Heinz-Dieter Ebbinghaus and Jörg Flum. As far as I recall it thoroughly covers both logics and their connection to P, respectively NP.

Now to your first question. Of course, as soon as both complexity classes had been characterized by logics, there were hopes to settle the P=NP question this way. Yet by now the problem has eluded this approach for several decades. One would need to pick some problem from NP and show that it is not expressible in FO(LFP) (first-order logic with least-fixed point operators). Essentially the only tool for proving non-expressibility are Ehrenfeucht–Fraïssé games. These games are notoriously hard to analyze in the presence of non-monadic second-order variables, which are needed in the case of FO(LFP). See also the paper https://eccc.weizmann.ac.il/report/2013/065/ by Yijia Chen and Jörg Flum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.