This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated.

Indeed, for first order logic they say "the language of a finite structure with a fixed signature including a linear order relation [with a suitable fixed point combinator]"; but it's not clear what this means, and it doesn't seem to be explained further.

For existential second order logic, the article just says "NP is the set of languages expressible in existential second-order logic" without any explanation: what does it mean for a language to be expressible in (existential) second-order logic ?

So my question is

What do these characterizations mean, precisely ?

To answer, you can assume I know what a formal language is, that I know what first order logic and existential second order logic, and that I know some decent amount of model theory. Note that I'm not asking for a proof of the characterization (although if there is a quick one I won't mind seeing it), just for a definition of the characterization.

  • $\begingroup$ I think you should raise a comment on Wikipedia Talk that this section of the article needs references and clarification. I'm personally disinclined to try to reverse engineer something meaningful from this part of the article as its stands (although someone on MSE more attuned with this particular area than me may have the answer at their finger-tips). $\endgroup$ – Rob Arthan May 16 at 21:06
  • $\begingroup$ You might have better luck looking at the page for descriptive complexity theory: en.wikipedia.org/wiki/Descriptive_complexity_theory $\endgroup$ – Ispil May 21 at 16:20
  • $\begingroup$ @Ispil thank you but this page still takes for granted the notion of "expressible in such logical system". I'll try to see if the references bring any light $\endgroup$ – Max May 21 at 16:26

A word $w$ over a finite alphabet $A$ has an associated (first-order) structure defined as follows. The vocabulary has a binary relation symbol $<$ and unary relation symbols $P_a$ for each letter $a\in A$. The structure associated to $w$ has underlying set $\{1,2,\dots,n\}$ where $n$ is the length of $w$; $<$ is interpreted as the usual ordering of the natural numbers $1,2,\dots,n$; and each $P_a$ is interpreted as the set of those $i\in\{1,2,\dots,n\}$ such that the $i$-th letter in $w$ is $a$.

A language $L$ is said to be expressed by a formula $\phi$ (in some logic) if and only if $L$ is the set of those words $w$ whose associated structure satisfies $\phi$.

EDIT: At the OP's suggestion, I'm putting here the link (originally in a comment) http://web.eecs.umich.edu/~gurevich/Opera/152.pdf to a paper describing various fixed-point operators and the associated logics.

  • $\begingroup$ Thank you ! Do you happen to know what the "suitable fixed point operator" is ? $\endgroup$ – Max May 21 at 21:54
  • 1
    $\begingroup$ @Max Unfortunately, there are numerous fixed-point operators, different ones will be "suitable" for different purposes, and a reasonable explanation would be too long to put here. Fortunately, there's a good deal of literature about these operators and the associated logics. In particular, there's a good survey by Dawar and Gurevich, available at web.eecs.umich.edu/~gurevich/Opera/152.pdf . You can find more material by googling "fixed-point logic". $\endgroup$ – Andreas Blass May 21 at 22:03
  • $\begingroup$ Thank you for the reference and the info; but I meant more specifically do you happen to know which fixed point operator gets you, when added to FOL, the class P of languages ? $\endgroup$ – Max May 21 at 22:06
  • $\begingroup$ Oh nevermind, the answer is actually given in the reference you suggested ! I will accept your answer and award you the bounty [when I can, that is, apparently, in 17 hours]; but could you add that link to the answer to make it more visible ? $\endgroup$ – Max May 21 at 22:11

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.